Binary Search Patterns
Classic Binary Search - A Quick Review
Binary search halves the search space each step. On a sorted array of n elements it finds a target in O(log n) time.
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
Simple - but the real power of binary search goes far beyond sorted arrays.
The Search Space Concept
Binary search works whenever you have a monotonic condition over a range. The "array" doesn't even need to exist - you just need a range [lo, hi] and a function that flips from False to True (or vice versa) at some boundary.
Search space: [lo .................. hi]
Condition: F F F F T T T T
^-- answer
Binary Search on Answer
Instead of searching an array, search the answer space. Ask: "Can I achieve result X?" If yes, try smaller; if no, try larger.
Example: Koko Eating Bananas
Koko has n piles of bananas and h hours. Find the minimum eating speed so she finishes in time.
def min_speed(piles, h):
lo, hi = 1, max(piles)
while lo < hi:
mid = (lo + hi) // 2
hours = sum((p + mid - 1) // mid for p in piles)
if hours <= h:
hi = mid # speed works, try slower
else:
lo = mid + 1 # too slow, go faster
return lo
The answer space is [1, max(piles)] and the condition is monotonic - higher speed always means fewer hours.
Discussion
Sign in to join the discussion