Binäre Suche über die Antwort
Der fortgeschrittene Trick: wenn ein Problem ein Maximum minimieren soll (oder umgekehrt) und Machbarkeit monoton ist, suche binär die Antwort selbst.
Deutsche Übersetzung in Arbeit
Diese Lektion ist noch nicht ins Deutsche übersetzt und wird daher auf Englisch angezeigt. Der Rest der Seite ist vollständig lokalisiert.
Auf dieser Seite
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…'.