Binary Search Pattern
Binary search discards half the remaining possibilities on each comparison. Beyond finding elements in sorted arrays, 'binary search on the answer' solves optimization problems by testing a monotonic predicate.
Typical complexity: O(log n) time, O(1) space
When to use it
- The data is sorted, or the answer space is monotonic.
- You can phrase the problem as 'is X feasible?' and feasibility only flips once.
- A linear scan is too slow (n is large).
Practice problems
Read the approach or generate an interactive, step-by-step lesson:
Deep dive
Binary Search Pattern: More Than Just Finding a Number
Understand classic binary search, boundary search, and the broader decision-based pattern that helps solve optimization problems in logarithmic time.
Master binary search by doing
codebrew.ai turns each problem into an interactive lesson — trace the algorithm variable by variable until the pattern clicks.
Start a free lesson