What it is
Binary search on the answer applies binary search not to an array's indices but to the space of possible answers to an optimization question — the smallest speed, capacity, or budget that satisfies some condition. The technique needs two things: a way to check "does this specific candidate value work" (the feasibility check), and a proof that feasibility is monotone — every value above (or below) a working candidate also works. Once both hold, the set of working values is a clean prefix or suffix of the range, and binary search finds its boundary in O(log(range)) evaluations of the feasibility check, regardless of how expensive it would be to try every candidate directly.
When it applies
- The problem asks for "the minimum X such that some condition holds" or "the maximum X such that some condition holds," and trying every candidate value directly would be too slow.
- You can write a feasibility check — often a single greedy pass — that answers "does value V satisfy the condition" cheaply, and you can argue that increasing (or decreasing) V never turns a working value into a non-working one.
- The problem never mentions "search" explicitly — that absence is itself a tell, since these problems are usually phrased as pure optimization ("minimum speed," "smallest capacity") rather than as a search over a data structure.
- It does not apply when there's no monotonicity — if a larger value can sometimes work and sometimes not depending on other factors (order can be rearranged, items can be reordered), the feasibility check itself becomes NP-hard or ill-defined, and binary search on the answer no longer has a clean boundary to find.
Tells in the problem
- "Find the minimum speed/rate at which everything finishes within a time limit" — checking one candidate speed is a cheap summation; a faster speed never takes longer, so the search is monotone.
- "Find the smallest capacity that lets everything be shipped/split within a fixed number of groups" — the feasibility check is a single greedy pass that packs greedily and counts groups used.
- Constraints given as huge ranges (values up to a billion, or an answer that could span from 1 to a huge sum) with a request for a solution far better than linear scan over that range — a strong hint that the intended technique divides that huge range logarithmically rather than walking it.
- The problem can be restated as "given a fixed candidate value, answer a yes/no question in roughly linear time" — whenever that restatement is natural and monotone, binary search over the candidate is usually the intended tool, even if the original phrasing gives no hint of searching.
- Two problems that look different on the surface (shipping capacity vs. splitting an array to minimize the largest partition sum) turning out to have the identical greedy-feasibility-plus-binary-search shape — recognizing that shape is more valuable than memorizing either individual problem.
The classic mistake
Trying every candidate value one at a time (or writing a DP over the full input) misses the problem's real signal: monotonicity — missing that "does this speed/capacity work" is a cheap, reusable check and that the answer sits at a clean boundary between infeasible and feasible values. A second, more subtle mistake is assuming the technique generalizes when the underlying assumption breaks: if the problem changes so that items can be reordered rather than processed in a fixed sequence, the simple greedy feasibility check often stops being exact (packing degenerates into bin packing, which is NP-hard), and forcing the same binary-search template onto it silently produces a wrong or unjustified answer. Before applying this pattern, explicitly verify monotonicity — "does making the candidate value larger only ever help, never hurt" — rather than assuming it because the problem superficially resembles one that worked.
Questions to start with
- Koko Eating Bananas — the cleanest introduction: the problem never mentions searching, and the whole exercise is noticing that "eating speed" is monotone against "hours needed."
- Capacity To Ship Packages Within D Days — the same shape with a greedy day-packing feasibility check, and an explicit discussion of why the fixed package order is what keeps the greedy check exact.
- Split Array Largest Sum — the same technique again, reframed as minimizing the largest partition sum, useful for seeing how differently-worded problems share one underlying template.