Review: Binary Search Problems

Binary search is important. The idea is simple.

But you wouldn’t believe how incredibly useful it would be.



Clarifications:

  1. Allow duplicate?
  2. What range you would choose to examine?
  3. How you can reduce the dataset into half?

Where Left/Right Would Be After Search?
l = [2, 3, 8, 12, 20, 35], target = 4

  1. Found. Target = 3. left == right, points to the value
  2. In the middle. Target = 11. [right, Target, left]. The previous step would be right==left, and the value is smaller than the target. Do you know why?
  3. Too small. Target = 1. [right(-1), left(0)]
  4. Too big. Target = 36. [right(len-1), left(len)]

Scenarios:

  1. Scenario: find whether target in the range. Guess Number Higher or Lower
class Solution(object):
    def guessNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n
        while left <= right:
            mid = int(left + (right-left)/2)
            v = guess(mid)
            if v == 0:
                return mid
            elif v == 1:
                left = mid + 1
            else:
                right = mid - 1
        return None

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left, right = 1, n
        while left < right:
            mid = int(left + (right-left)/2)
            if isBadVersion(mid):
                right = mid
            else:
                left = mid + 1

        # left == right
        return left if isBadVersion(left) else None

The most impressive problems to me:

See all binarysearch problems: #binarysearch.

See more blog_posts.

linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.