Binary Search on the Answer
The advanced trick: when a problem asks to minimize a maximum (or vice versa) and feasibility is monotonic, binary-search the answer itself.
On this page
Here's the binary-search insight that separates strong candidates from the rest: you can binary-search over things that aren't arrays at all. When a problem asks you to minimize a maximum (or maximize a minimum) and there's a monotonic "is this feasible?" test, you can binary-search the answer itself.
The pattern: search the answer space
Some problems don't ask "where is x?" but "what's the smallest capacity / largest minimum / minimum time
that works?" If you can write a function feasible(x) that returns true/false, and feasibility is
monotonic (once true, it stays true as x increases - or vice versa), you can binary-search over the
range of possible answers:
// generic shape: find the smallest x for which feasible(x) is true
int lo = minPossible, hi = maxPossible;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (feasible(mid)) hi = mid; // mid works → answer is mid or smaller
else lo = mid + 1; // mid too small → need larger
}
return lo; // smallest feasible answerYou're not searching an array - you're searching the numeric range of candidate answers, using feasibility as the comparison. This turns "try every possible answer" (O(answer range)) into O(log(range) × cost of feasible).
A concrete example: shipping capacity
"Given package weights and D days, find the minimum ship capacity to deliver all packages in order
within D days." The answer lies between max(weight) (must fit the heaviest) and sum(weights) (one
day). Feasibility - "can we finish in D days with capacity c?" - is monotonic: more capacity never hurts.
So binary-search the capacity:
int shipWithinDays(int[] weights, int D) {
int lo = Arrays.stream(weights).max().getAsInt();
int hi = Arrays.stream(weights).sum();
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (daysNeeded(weights, mid) <= D) hi = mid; // capacity mid works
else lo = mid + 1;
}
return lo;
}
// daysNeeded greedily counts days for a given capacity — the feasibility checkThe tell: 'minimize the maximum' or 'maximize the minimum'
Reach for binary-search-on-answer when a problem says 'minimum largest…', 'smallest capacity/speed/time such that…', 'split into k parts minimizing the biggest part', or 'largest minimum distance.' The signals are an optimization over a numeric range plus a monotonic feasibility check you can write as a simple simulation.
You want the lowest thermostat setting at which the house still feels warm enough. You can't compute it directly, but you can test any setting: pick one and feel whether it's warm enough. And it's monotonic - higher settings are always at least as warm. So you binary-search the temperature: try the middle of the range, and if it's warm enough, everything above works too, so search lower; if not, search higher. You converge on the exact coldest-yet-comfortable setting in a few tries, testing settings rather than searching a list.
Koko eats bananas from piles at some speed k (bananas/hour); with each pile she eats k per hour, moving to the next pile only when the current is done. Given the piles and H hours, find the minimum speed k to finish within H hours. Frame this as binary-search-on-answer.
When can you 'binary-search the answer' to a problem?
Key takeaways
- Binary search isn't limited to arrays - you can search a numeric range of candidate answers.
- It applies when feasibility is monotonic: once feasible(x) is true, it stays true as x increases (or decreases).
- Write a feasible(x) simulation, then binary-search the smallest/largest x that passes.
- This turns 'try every answer' into O(log(range) x feasibility cost).
- The tell is 'minimize the maximum', 'maximize the minimum', or 'smallest capacity/speed/time such that…'.