Binary Search on the Answer

The 10-second versionCopy Anchor Link

Sometimes you can't find the answer by looking in the input — you have to look at the range of possible answers and binary-search over that instead. The move works whenever you can write a feasibility check: "does a candidate answer X work?" And it works fast whenever that check is monotone — if X works, every larger guess works too, or every smaller one does. Then the answers form a clean yes/no boundary, and binary search finds it in O(log range) checks instead of testing every candidate.

Why this existedCopy Anchor Link

The technique is built on top of binary search, one of the oldest algorithms in computing — and, famously, one of the hardest to get right.

• 1946 — John Mauchly sketches binary search in the Moore School Lectures, describing how to find an entry in a sorted table by halving the interval.
• 1962 — Hermann Bottenbruch publishes the first correct binary-search algorithm. The original versions were subtly buggy (the midpoint computation overflowed; the bounds looped forever) — this history is why the phrase "binary search is deceptively simple" exists.
• 1979 — Nimrod Megiddo formalizes parametric search, the idea of searching over a parameter rather than over stored data — the theoretical ancestor of "binary search the answer."
• Modern — the pattern is a staple of algorithm design: whenever a problem says minimize the maximum or find the smallest that satisfies, you binary-search the answer.

Why it mattered: binary search was invented for a sorted table of data. The leap here is realizing the thing you sort and halve doesn't have to be stored at all — it can be a virtual range of candidate answers, as long as you can test one in the middle. That generalization is what turns "impossible at 10⁹ candidates" into thirty checks.

Inside the inventor's headCopy Anchor Link

Here's the problem pattern that forces this trick. Take "ship all packages within D days": you have package weights and a ship capacity, and you want the smallest capacity that can ship everything in time. Or "split an array into k parts, minimizing the largest part." Both ask you to minimize a maximum — the answer isn't a position in the array, it's a number.

The straightforward attack guesses every possible capacity from small to large and checks it:

// can we ship everything within `days` at capacity `cap`?function feasible(w, cap, days) {  let used = 1, load = 0;  for (const x of w) {    if (x > cap) return false;    if (load + x > cap) { used++; load = 0; }    load += x;  }  return used <= days;}// try capacities from the minimum upward — slow when the sums are largefunction shipNaive(w, days) {  const lo = Math.max(...w);  const hi = w.reduce((a, b) => a + b, 0);  for (let cap = lo; cap <= hi; cap++)    if (feasible(w, cap, days)) return cap;  return hi;}

Each check is O(n), but the candidate range can be enormous — capacities run up to the sum of all weights, easily 10⁹. So a linear scan is O(n · range), hopeless. But stare at the feasibility function and something jumps out:

If capacity 100 can ship everything in time, then capacity 101 definitely can too.

Feasibility is monotone — once it becomes true, it stays true forever. So the candidate space looks like a long runway of no, no, no, …, yes, yes, yes…, and all you want is the first yes.

That's the "aha." You're not searching stored data — you're searching a property. The predicate tells you which half the boundary is in, and the monotonicity guarantees the predicate won't "flip back." That's exactly the precondition plain binary search needs, just applied to a virtual range instead of an array.

The final approachCopy Anchor Link

The algorithmCopy Anchor Link

Pick a lower and upper bound for the answer. Repeatedly test the midpoint; if it's feasible, the answer is at or below it, so move the high bound down; otherwise move the low bound up. When the bounds meet, that's the smallest feasible value.

The invariantsCopy Anchor Link

• Bounds are honest. hi is always known-feasible and lo - 1 is always known-infeasible (everything below lo has been ruled out), so the boundary lives in [lo, hi].
• Monotone predicate. feasible(x) can only transition from false to true as x grows — never back. This is the precondition that makes the halving valid.
• Termination. Each step shrinks [lo, hi] by roughly half, so it ends in O(log(range)) iterations. The loop exits with lo == hi, the smallest feasible answer.

The one thing to get right: the shape of the search. This is the "find the first true" variant (hi = mid on success, lo = mid + 1 on failure) — not the "find any true" variant. Use mid derived as lo + (hi - lo) / 2 to avoid overflow, exactly as the plain binary-search page warns.

A worked traceCopy Anchor Link

Ship weights [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] within 5 days. The answer must be at least the heaviest package (10) and at most the total (55). Search [10, 55]:

Six feasibility checks replaced scanning 46 candidate capacities — and the gap only widens as the range grows.

It in codeCopy Anchor Link

// can we ship everything within `days` at capacity `cap`?function feasible(w, cap, days) {  let used = 1, load = 0;  for (const x of w) {    if (x > cap) return false;    if (load + x > cap) { used++; load = 0; }    load += x;  }  return used <= days;}// smallest capacity that ships within `days`function shipWithinDays(w, days) {  let lo = Math.max(...w), hi = w.reduce((a, b) => a + b, 0);  while (lo < hi) {    const mid = Math.floor(lo + (hi - lo) / 2);    if (feasible(w, mid, days)) hi = mid;    else lo = mid + 1;  }  return lo;}

The same shape, a different predicateCopy Anchor Link

The predicate is the only thing that changes from problem to problem. "Split the array into k parts, minimizing the largest part" uses a greedy "how many parts does this limit force?" check:

// can we split into at most k parts, each summing to at most `limit`?function canSplit(a, limit, k) {  let run = 0, parts = 1;  for (const x of a) {    if (run + x > limit) { parts++; run = 0; }    run += x;  }  return parts <= k;}function splitArray(a, k) {  let lo = Math.max(...a), hi = a.reduce((x, y) => x + y, 0);  while (lo < hi) {    const mid = Math.floor(lo + (hi - lo) / 2);    if (canSplit(a, mid, k)) hi = mid;    else lo = mid + 1;  }  return lo;}

CostCopy Anchor Link

range is the span between the lower and upper bounds — the sum of the array, a max value, and so on. Even at 10⁹, that's about thirty checks.

Where you meet it todayCopy Anchor Link

• Logistics and capacity planning. "Fewest trucks to deliver everything," "minimum server capacity to handle the load in time," "smallest bandwidth to finish the upload by the deadline."
• Scheduling and bin-packing. Minimizing the maximum load across machines — the makespan problem — is a monotone feasibility search whenever the assignment rule is greedy.
• Rate and threshold tuning. "Slowest eating speed that finishes in h hours," "largest minimum distance between placed items," "smallest divisor so the sum stays under a limit" — all monotone predicates.
• Search and ranking. Picking a cutoff score that leaves a target number of results is a binary search over the score range, not over a stored list.

// hours needed to eat every pile at speed `s`function hoursNeeded(p, s) {  let h = 0;  for (const x of p) h += Math.ceil(x / s);  return h;}function minEatingSpeed(p, h) {  let lo = 1, hi = Math.max(...p);  while (lo < hi) {    const mid = Math.floor(lo + (hi - lo) / 2);    if (hoursNeeded(p, mid) <= h) hi = mid;    else lo = mid + 1;  }  return lo;}

Notice how familiar it looks: a lower and upper bound, a midpoint, a predicate, and the same hi = mid / lo = mid + 1 dance. Once you can write the predicate, you've solved the problem — the search is mechanical.

RecapCopy Anchor Link

• Binary search on the answer searches the range of possible answers, not the input.
• It needs exactly two things: a feasibility predicate and monotonicity (once true, always true, or once false, always false).
• Use the "first true" variant — hi = mid on success, lo = mid + 1 on failure — with mid = lo + (hi - lo) / 2 to dodge overflow.
• The whole cost is O(n · log range): an O(n) check repeated O(log range) times.
• If a problem says minimize the maximum or find the smallest that works, think "binary search the answer" and go write the predicate.

Next up: Binary Trees & Traversals — leaving flat arrays behind for structures where everything is a recursive decision.