Binary search on the answer
hardThere is no sorted array here at all. What is sorted is the feasibility check - and a monotone boundary is the only thing binary search actually needs. 'Minimise the maximum' problems all reduce to this.
O(log(range) × cost of the check)Space O(1)Saved in this browser - no sign-up, nothing sent anywhere.
How binary search on the answer works
There is no array to search. The question is 'what is the smallest ship capacity that clears these packages in 5 days?' - and the candidate capacities form a numeric range, here 10 through 55. What replaces sorted order is a monotone predicate: if capacity C is enough, every capacity above C is enough too. False, false, false, true, true, true - that boundary is all binary search ever needed.
The loop is lowerBound in disguise: while lo < hi, test feasible(mid) - a greedy pass that packs packages into days without splitting - then set hi = mid when it works, because mid might be the answer, or lo = mid + 1 when it does not. The bounds must be provable: lo = max(weights), since a smaller ship cannot lift the heaviest package, and hi = sum(weights), since one day always suffices at that size.
The pattern hides behind phrasing: 'minimise the maximum', 'maximise the minimum', 'smallest k such that the check passes'. The recipe never changes - write the feasibility check, argue it is monotone, binary search the boundary. Writing the check is usually the easy part; noticing that the problem is a search is the skill being tested.
Step by step
- Ship packages weighing 1 through 10 - 55 units in total - within 5 days. Capacity must lie in [10, 55]: 46 candidates.
- Try mid = 32: the greedy pass fills just 2 days. Feasible - so 32 and everything above it works. hi = 32.
- Try 21: 3 days, feasible, hi = 21. Try 15: exactly 5 days - still feasible, so hi = 15.
- Try 12: the greedy pass now needs 6 days. Infeasible - no capacity this small can ever work. lo = 13.
- Try 14: the greedy still needs 6 days - infeasible again, so lo = 15 and the pointers meet.
- The answer is 15 - the smallest workable capacity, found with 5 feasibility checks instead of testing all 46 candidates one by one.
Complexity
| Worst case time | O(log(range) × cost of the check) |
|---|---|
| Space | O(1) |
The predicate must be monotone: once true, true for everything larger.
Reference implementation
Python
def ship_within_days(weights, days):
def feasible(cap):
need, load = 1, 0
for w in weights:
if load + w > cap:
need += 1
load = 0
load += w
return need <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = lo + (hi - lo) // 2
if feasible(mid):
hi = mid # mid works - can we do better?
else:
lo = mid + 1 # mid is too small
return loJavaScript
function shipWithinDays(weights, days) {
const feasible = (cap) => {
let need = 1, load = 0;
for (const w of weights) {
if (load + w > cap) { need++; load = 0; }
load += w;
}
return need <= days;
};
let lo = Math.max(...weights);
let hi = weights.reduce((s, w) => s + w, 0);
while (lo < hi) {
const mid = lo + ((hi - lo) >> 1);
if (feasible(mid)) hi = mid; else lo = mid + 1;
}
return lo;
}Worth noticing
Search the answer space, not the array
There is no sorted array here at all. What is sorted is the *predicate*: if capacity C works, so does every capacity above it. That monotone boundary is the only thing binary search actually needs.
Spotting the pattern
'Minimise the maximum', 'maximise the minimum', 'smallest k such that…' - all the same shape. Write a feasibility check, prove it is monotone, then binary search the boundary. The check is usually the easy part.
The bounds have to be provable
lo is the heaviest package (any smaller ship cannot carry it at all), hi is the total (one day is always enough). Both are obviously correct, which is what makes the search safe.
Common pitfalls
- A predicate that is not actually monotone. The loop still converges and returns a number - a meaningless one, with no error. Prove 'if C works, C + 1 works' before searching.
- Unprovable bounds. Starting lo below max(weights) lets the greedy check report success for capacities that cannot even hold one package - the boundary you converge to is fiction.
- Using the lo <= hi, return -1 pattern from membership search. Minimising over a predicate needs lo < hi with hi = mid - writing hi = mid - 1 on a feasible mid can discard the optimum itself.
- An off-by-one inside the check - load + w > cap versus >= - shifts the boundary by one and returns a plausible wrong answer. Test feasible() on hand-computed cases first.
- Searching a continuous answer space with the integer loop. Real-valued answers need an epsilon tolerance or a fixed iteration count, or the while loop never terminates.
Where it is used
- The interview family: capacity to ship packages in D days, Koko eating bananas, split array largest sum, aggressive cows.
- git bisect - the first bad commit is a monotone boundary over history, found in log n checkouts.
- Capacity planning: the smallest machine count or rate limit that still meets a target, when each candidate can be checked by simulation.
- Any 'minimise the maximum' or 'maximise the minimum' contest problem - the phrasing is practically a spoiler.
Frequently asked questions
What is the time and space complexity of binary search on the answer?
O(log(range) × cost of the check): the loop runs log of the answer range's width, and each round pays for one feasibility check. Here the range 10..55 costs 5 checks, each an O(n) greedy pass over the packages. Space is O(1) beyond the check itself.
How do I recognise a binary search on the answer problem?
The asks are formulaic: minimise a maximum, maximise a minimum, find the smallest value passing a test. Then confirm two things - the answer lives in a numeric range with provable ends, and feasibility is monotone in that number. If both hold, binary search the boundary instead of the input.
Why does the predicate have to be monotone?
Monotonicity plays the role sorted order played in ordinary binary search. Discarding half the range is only sound if one test speaks for everything beyond it - feasible(mid) failing must rule out every smaller capacity. Without that guarantee, the discarded half can contain the true answer and the result is garbage.
Why do lo and hi start at max(weights) and sum(weights)?
Because both ends are provable, which is what makes the search safe. Any capacity below the heaviest package cannot carry it at all, so no smaller answer exists; the total weight always ships in a single day, so a valid answer certainly lies inside the range. Sloppy bounds silently corrupt the boundary the loop converges to.