Binary search
Search the answer, not the array: halve a monotone predicate until one candidate is left.
When it applies
Binary search applies whenever a yes/no test is monotone: once it turns true it stays true. That covers the obvious case of a sorted array, and the less obvious one where the answer is a number and checking a candidate is cheaper than constructing it.
Signals: "minimum capacity", "smallest k such that", "maximise the minimum", "first index where". Write the check first, prove it is monotone, then search.
The template
Write this from memory. Every problem in this section is a specialisation of it, and most bugs come from deviating without a reason.
lo, hi = low_bound, high_bound
while lo < hi: # invariant: the answer is in [lo, hi]
mid = (lo + hi) // 2
if feasible(mid):
hi = mid # mid might be the answer; keep it
else:
lo = mid + 1 # mid is too small
return lolong long lo = lowBound, hi = highBound;
while (lo < hi) {
long long mid = lo + (hi - lo) / 2; // no overflow
if (feasible(mid)) hi = mid; else lo = mid + 1;
}
return lo;long lo = lowBound, hi = highBound;
while (lo < hi) {
long mid = lo + (hi - lo) / 2;
if (feasible(mid)) hi = mid; else lo = mid + 1;
}
return lo;let lo = lowBound, hi = highBound;
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (feasible(mid)) hi = mid; else lo = mid + 1;
}
return lo;let (mut lo, mut hi) = (low_bound, high_bound);
while lo < hi {
let mid = lo + (hi - lo) / 2;
if feasible(mid) { hi = mid } else { lo = mid + 1 }
}
losearch lo hi
| lo >= hi = lo
| feasible mid = search lo mid
| otherwise = search (mid + 1) hi
where mid = lo + (hi - lo) `div` 2Problems
Minimum of a rotated sorted array
The input is not sorted, so the usual comparison is useless. Compare against the right end instead.
Open the problem → Medium20 minSmallest ship that clears the backlog in D days
When the answer is a number and "is X enough?" is easy to check, search over answers rather than over data.
Open the problem →Or sit a timed interview: a fixed window, limited submissions, and a report at the end.