Developer/DesignPatterns/AlgorithmsDataStructures/SearchingAlgorithms/Fundamentals/binary-search-on-the-answer

Binary Search on the Answer

Concept

Textbook binary search finds a target value inside an already-sorted array by repeatedly halving the search range. The more broadly useful version of the same idea drops the "sorted array" requirement entirely: binary search on the answer applies whenever the set of possible answers — not the input data — has a monotonic structure, meaning there's some threshold value such that every candidate on one side of it is feasible and every candidate on the other side is not. Instead of searching a data structure, the algorithm searches the space of possible outputs directly, using a feasibility function — a predicate that, given a candidate answer, determines whether it's achievable — as the comparison at each step.

The recognizable shape: the problem asks for a minimum or maximum value satisfying some condition ("minimum number of days to ship all packages," "maximum minimum distance between placed items," "smallest capacity such that everything fits"), and checking whether a specific candidate value works is computationally cheap (often O(n) or better) even though searching for the optimal value directly would require checking every candidate one at a time. If feasibility is monotonic in the candidate value — every value above the answer is feasible, every value below it is not (or vice versa for a maximize-the-minimum problem) — binary search collapses what would be a linear or exponential search over candidates into a logarithmic one: binary search the candidate range, and at each midpoint call the feasibility function to decide which half of the range to keep.

This reframing is what makes many problems that don't superficially look like "search a sorted array" solvable with the same O(log(range)) technique — the array being searched is conceptual (the space of possible answers), not a literal data structure in memory.

Tradeoffs

Approach	When it applies	Cost
Linear scan over candidate answers	Always correct, no monotonicity requirement	O(range × feasibility-check-cost) — often too slow when the range is large
Binary search on the answer	Requires a monotonic feasibility function	O(log(range) × feasibility-check-cost) — the standard win, but incorrect if monotonicity doesn't actually hold
Ternary search	Unimodal (single peak/valley) but non-monotonic objective functions	Still O(log(range)) but a different, more error-prone template; doesn't apply to plain monotonic feasibility problems — reaching for it there is unnecessary complexity

The core precondition — monotonicity of the feasibility function — is not optional and not always obvious from the problem statement; it has to be verified (or constructed) before applying the technique, the same way the greedy-choice property has to be verified before trusting a greedy algorithm.

When to use / when not to

Use whenever a problem asks to minimize a maximum or maximize a minimum over some quantity, and a candidate value for that quantity can be checked for feasibility efficiently and independently of other candidates.
Recognizable variants beyond literal sorted-array search: "search on the answer" problems (minimum capacity to ship within D days, Koko-eating-bananas-style minimum eating speed, minimum largest-page-count when splitting a book across binders), and structural variants on the input itself (searching a rotated sorted array, finding the first/last occurrence of a value, finding a peak element) — all reduce to the same halving-with-a-decision-predicate template even though only the last group looks like classic binary search on the surface.
Don't reach for it when the feasibility function isn't actually monotonic — verify this explicitly (a quick proof sketch or a few hand-checked boundary cases), because applying binary search to a non-monotonic predicate produces a wrong answer that still terminates and still returns something, which makes the bug easy to miss.
Don't use it when checking a single candidate's feasibility is itself as expensive as just computing the true answer directly (e.g., via a closed-form formula or a single linear pass) — the technique only pays for itself when the feasibility check is cheap relative to the full candidate space.

Common pitfall

Off-by-one errors in the loop boundaries and midpoint calculation — this family of bugs is disproportionately common in binary search compared to other algorithms precisely because there are several subtly different correct templates (lo < hi vs. lo <= hi, mid = lo + (hi - lo) / 2 vs. naive (lo + hi) / 2 which can overflow in fixed-width integer languages, updating to mid vs. mid + 1/mid - 1) and mixing pieces from different templates produces code that looks plausible, compiles, and passes some test cases while looping infinitely or returning an off-by-one-wrong boundary on others. The reliable fix is picking one template (inclusive or exclusive range, consistently) and verifying it converges by hand-tracing a 2-3 element case, rather than mixing conventions from memory.

Engineering Lens

The "search on the answer" reframing is a good example of the broader pattern-recognition skill that matters more than memorizing any specific algorithm: recognizing that a problem's output space has exploitable structure even when its input doesn't look like the thing binary search is normally taught on. That recognition — "can I turn this optimization into a feasibility check, and is that check monotonic?" — generalizes past interview problems into real capacity-planning and resource-allocation code: deciding the minimum number of workers/instances needed to clear a backlog within an SLA, or the minimum batch size that keeps a pipeline under a latency budget, are both literally the same technique applied to production infrastructure sizing rather than a coding problem.