Binary Search
The Intuition
You know the number guessing game? "I'm thinking of a number between 1 and 100." You guess 50. "Too high." Now you know it's between 1 and 49. You guess 25. "Too low." Between 26 and 49. Every guess cuts the remaining possibilities in half. Seven guesses and you can nail any number from 1 to 100. Twenty guesses handles over a million.
That's binary search at its core. Look at the middle, decide which half to throw away, repeat. But here's what trips people up: sorted arrays are just the obvious use case. The real power shows up when you search on an answer space. Imagine a problem like "what's the minimum speed to finish all tasks in D days?" You don't search through the tasks. You search through possible speeds. Pick a speed in the middle, check if it works, throw away half the speeds. The answer space just needs to be monotonic: below some threshold it fails, above it succeeds.
Searching sorted arrays, finding boundaries (first/last occurrence), minimizing/maximizing an answer with a feasibility check, or searching in rotated sorted arrays.
- Unsorted data you can't sort
- Non-monotonic conditions
- Need to find all matches (use linear scan)
Variations:
- Standard search: Find exact target in sorted array.
- Lower/upper bound: Find the first or last position of target.
- Search on answer: Binary search the result space when feasibility is monotonic (e.g., "minimum capacity to ship packages in D days").
- empty array
- single element
- all duplicates
- target absent
Key Points
- •Requires sorted input or monotonic condition
- •Use left + (right - left) // 2 to avoid overflow
- •Decide which half to discard based on the condition
- •Boundary variants: find leftmost/rightmost occurrence
- •Can search on answer space (binary search on result)
Code Template
1 def binary_search(arr, target):
2 """Standard binary search for target."""
3 left, right = 0, len(arr) - 1
4 while left <= right:
5 mid = left + (right - left) // 2
6 if arr[mid] == target:
7 return mid
8 elif arr[mid] < target:
9 left = mid + 1
10 else:
11 right = mid - 1
12 return -1
13
14 def lower_bound(arr, target):
15 """Find leftmost index where arr[i] >= target."""
16 left, right = 0, len(arr)
17 while left < right:
18 mid = left + (right - left) // 2
19 if arr[mid] < target:
20 left = mid + 1
21 else:
22 right = mid
23 return left
24
25 def search_on_answer(lo, hi, is_feasible):
26 """Binary search on answer: find minimum feasible value."""
27 while lo < hi:
28 mid = lo + (hi - lo) // 2
29 if is_feasible(mid):
30 hi = mid
31 else:
32 lo = mid + 1
33 return loCommon Mistakes
- Integer overflow with (left + right) / 2
- Infinite loop from incorrect mid calculation or bounds update
- Off-by-one error: left <= right vs left < right