Classic binary search finds a value in a sorted array. Binary search on answers finds the smallest x such that some predicate ok(x) is true, when ok is monotonic: once it becomes true, it stays true.
That covers a shocking amount of contest problems: minimum capacity to ship packages, first day you can make m products, smallest maximum edge on a path, cutting wood, aggressive cows…
// ok[i] is false* then true*. Return first index where ok(i) is true.
function firstTrue(lo, hi, ok) {
// search in [lo, hi), invariant: ok(lo-1) is false, ok(hi) is true
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (ok(mid)) hi = mid;
else lo = mid + 1;
}
return lo;
}To use the pattern in the wild:
- Phrase the answer as a number
xon a known range. - Write
ok(x)so it is true iffxis feasible. - Prove:
ok(x)impliesok(x+1)(or the opposite, and search the last true). - Binary search. Check
okatmidby simulating — often a greedy O(n) pass. - Total time
O(n log X)whereXis the value range (often 10⁹ or 10¹⁸).
Checks 0/2