Pattern 04
Binary Search
Cut the search space in half every step instead of scanning one by one.
When to use
Use when the search space is sorted, monotonic, or can be split in half based on a true/false condition. 'Find the minimum X that satisfies a condition' is almost always binary search on the answer.
Core intuition
Check the middle value. Decide if the answer is in the left half or right half. Discard the other half. Repeat. Each step eliminates half the remaining work, giving O(log n) instead of O(n).
Template
def binary_search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
# Search on answer template
def search_on_answer(lo, hi):
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
return loSuggested problems
Key takeaways
- ›Sorted or monotonic input → binary search alert
- ›Check mid, then decide: go left or go right
- ›Use left <= right for exact search, left < right for boundary search
- ›'Minimum X that works' → binary search on the answer space
- ›Off-by-one errors are common — trace a small example carefully
You'll see this when...
- ›Sorted array, find target or position
- ›Rotated sorted array
- ›Find first or last occurrence
- ›'Minimum viable' or 'maximum possible' value
- ›Can you tell if a value is feasible? Then binary search on it