← All patterns
Binary Search (incl. on answer space)
Halve the search space each step; applies not just to sorted arrays but to any monotonic predicate space.
When to use it
- Classic search in a sorted array.
- 'Binary search on the answer': minimize/maximize a value where feasibility is monotonic (e.g. minimum capacity to ship packages in D days).
Signals in the problem statement
- Sorted input, or a monotonic yes/no feasibility function over a numeric range.
Common pitfalls
- Infinite loops from incorrect midpoint/bound updates (`lo = mid` vs `lo = mid + 1`).
- Not recognizing a disguised binary-search-on-answer problem because the array itself isn't sorted.
Practice Problems
Koko Eating Bananas (Binary Search on Answer)
MediumAsked at: Google, Amazon
Koko has piles of bananas and h hours. Find the minimum eating speed k so she can finish all piles within h hours.
Time: O(n log(max(piles))) · Space: O(1)