Binary search is important. The idea is simple.
But you wouldn’t believe how incredibly useful it would be.
- Allow duplicate?
- What range you would choose to examine?
- How you can reduce the dataset into half?
Where Left/Right Would Be After Search?
l = [2, 3, 8, 12, 20, 35], target = 4
- Found. Target = 3. left == right, points to the value
- 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?
- Too small. Target = 1. [right(-1), left(0)]
- Too big. Target = 36. [right(len-1), left(len)]
- 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:
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.