Binary Search
Halve the search space each step to find targets or boundaries in O(log n) time on sorted or monotonic data.
- • Sorted array
- • Finding boundary/threshold
- • Minimizing/maximizing with monotonic check
- • Search space reduction
- • Unsorted, non-monotonic data
- • Need to find all occurrences
- • Off-by-one in left/right bounds
- • Infinite loops from wrong mid calculation
- • Wrong condition for left vs right boundary
Key Invariant
Each iteration eliminates half the remaining candidates — the search predicate must be monotonic