All patterns
Binary Search
Halve the search space using a monotone yes/no question.
time O(log n) × cost of checkspace O(1)
What it is
If a predicate flips from false to true exactly once across a range, you can find the flip point in O(log n). It works on sorted arrays and also on answer spaces such as “smallest capacity that works”.
When to reach for it
- Sorted or rotated sorted data
- Minimize the maximum or maximize the minimum
- Find the first index satisfying a condition
Clues in the problem
- Target complexity O(log n)
- A feasibility check that is monotone in the answer
- n up to 10⁹ or more
Template
def first_true(lo, hi, ok):# smallest x in [lo, hi] with ok(x) True; ok is monotonewhile lo < hi:mid = lo + (hi - lo) // 2 # avoids overflowif ok(mid):hi = midelse:lo = mid + 1return lo
Practice problems
- Search in Rotated Sorted Array
- Koko Eating Bananas
- Capacity To Ship Packages
- Find First and Last Position
Common mistakes
- (lo + hi) / 2 overflow in Java or C++
- Infinite loop from lo = mid when mid == lo
- Applying it when the predicate is not monotone