Binary Search
Halve the search space every step. On any monotonic predicate — not just sorted arrays — this finds the boundary in O(log n).
Key ideas
- —Binary search needs a monotonic property, not literally a sorted array.
- —Decide on a half-open or closed interval and keep it consistent to avoid off-by-one bugs.
- —You can binary search on the answer when "is X feasible?" is monotone.
Beyond sorted arrays
The real precondition is monotonicity: there is some threshold below which a predicate is false and above which it is true. Finding the first version that is broken, or the smallest capacity that finishes a job in time, both fit this shape even though no array is being scanned. Frame the question as "what is the boundary?" and binary search applies.
Loop invariants and off-by-one
Pick one convention and stick to it: a closed interval [lo, hi] loops while lo <= hi and moves past mid; a half-open interval [lo, hi) loops while lo < hi. Most binary search bugs come from mixing conventions or updating the wrong bound. Compute mid as lo + (hi - lo) / 2 to avoid overflow in languages with fixed-width integers.
Practice this
Sources
- Binary search algorithmWikipedia
- bisect — array bisection algorithmPython docs