CONCEPT · Pupil
Binary search
also bsearch · lower bound · search on answer
Halve a monotone search space. Either the array is sorted, or the answer is a number whose feasibility predicate flips once.
Intuition
Each probe must discard half of the remaining candidates. If ok(mid) does not let you discard a side, it is not binary search.
When to reach for it
- Lower/upper bound in a sorted array
- Minimize the maximum / maximize the minimum
- First day / first index a condition holds
Usual pits
- Non-monotone predicates
- Overflow in (lo+hi)/2 — use lo + (hi-lo)/2
- Infinite loops when lo/hi do not move