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

• Scenario: find the first target. First Bad Version

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

• Scenario: find the first target
• Scenario: Find smallest letter greater than target. Find Smallest Letter Greater Than Target

The most impressive problems to me:

• Find Right Interval
• Search for a Range
• Sqrt(x)

See all binarysearch problems: #binarysearch.

• Review: Binary Search Problems
• LintCode: Single Number IV
• LintCode: Leftmost One
• LintCode: Count Negative Number
• Leetcode: Valid Perfect Square
• Leetcode: Sqrt(x)
• Leetcode: Single Element in a Sorted Array
• Leetcode: Search Insert Position
• Leetcode: Search in Rotated Sorted Array II
• Leetcode: Search in Rotated Sorted Array
• Leetcode: Search in a Sorted Array of Unknown Size
• Leetcode: Search for a Range
• Leetcode: Search a 2D Matrix II
• Leetcode: Search a 2D Matrix
• Leetcode: Preimage Size of Factorial Zeroes Function
• Leetcode: Most Profit Assigning Work
• Leetcode: Lowest Common Ancestor of a Binary Search Tree
• Leetcode: Kth Smallest Element in a Sorted Matrix
• Leetcode: Guess Number Higher or Lower
• Leetcode: First Bad Version
• Leetcode: Find the Duplicate Number
• Leetcode: Find Smallest Letter Greater Than Target
• Leetcode: Find Minimum in Rotated Sorted Array II
• Leetcode: Find Minimum in Rotated Sorted Array
• Leetcode: Closest Binary Search Tree Value
• Leetcode: Binary Search
• Leetcode: Advantage Shuffle

See more blog_posts.

---

Post Views: 6

Share It, If You Like It.