Binary Search
Mindmap
Problem Categories
Anatomy: One Template to Rule Them All
Almost every problem here is the same lower-bound loop with the comparison swapped out. Master this shape and the variants become trivial.
The only things that change between problems:
| Knob | Options | Why it changes |
|---|---|---|
What predicate(mid) tests | arr[mid] < target, cited(mid) > arr[mid], canNotShip(mid), ... | The "thing" being searched - a value, a boundary, or a feasibility answer |
hi start | len(arr) - 1 vs len(arr) | Whether the answer can sit one past the last index (insert positions, missing counts) |
lo < hi vs lo <= hi | survivor check vs in-loop return | Lower-bound style returns one survivor; the <= style returns on a direct hit |
| Glide direction | < for leftmost, <= for rightmost | How duplicates of target are handled |
Three things we ever search
- An index - the value lives directly in a sorted array (
704,35, peaks, rotated). - A boundary - we want where a value would go, then read the
[left, right)span (thebisect_*toolkit,34). - An answer value - the array isn't searched at all; we bisect a numeric range and verify each candidate with a monotone predicate (
875,1011,sqrt).
When the input isn't sorted
If the predicate is monotone but the array isn't, an O(N log N) sort up front still lands us in O(N log N) overall - which is why "sort, then bisect" appears throughout this section.