Search on the Answer
Sometimes the thing to find is not in the array at all. What is the smallest ship capacity that moves these packages in time, or the slowest speed that still finishes? The trick is to notice that the question 'does x work?' flips from no to yes exactly once as x grows. That is a sorted sequence of answers, even though nobody wrote it down, so it can be binary searched: probe the middle capacity, run a cheap feasibility check on the data, and throw away the half that cannot hold the answer.
Ship these packages in order within 5 days; find the least capacity that works. The answer is at least the heaviest package, 10, and at most everything at once, 55. A bigger capacity never needs more days, so feasibility is monotonic and the range can be binary searched.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 5, with their answers.
Capacity 32 needs 2 days against a limit of 5. Which half keeps the answer?
Answer: Lower half, hi = 32. Feasible means the least capacity is at most 32.
Capacity 21 needs 3 days against a limit of 5. Which half keeps the answer?
Answer: Lower half, hi = 21. Feasible means the least capacity is at most 21.
Capacity 15 needs 5 days against a limit of 5. Which half keeps the answer?
Answer: Lower half, hi = 15. Feasible means the least capacity is at most 15.
Capacity 12 needs 6 days against a limit of 5. Which half keeps the answer?
Answer: Upper half, lo = 13. Infeasible means every capacity up to 12 fails too.
Capacity 14 needs 6 days against a limit of 5. Which half keeps the answer?
Answer: Upper half, lo = 15. Infeasible means every capacity up to 14 fails too.
How it runs, step by step
Ship these packages in order within 5 days; find the least capacity that works. The answer is at least the heaviest package, 10, and at most everything at once, 55. A bigger capacity never needs more days, so feasibility is monotonic and the range can be binary searched.
Least ship capacity for 10 packages in 5 days, range 10 to 55.
Range 10 to 55, probe capacity 32. Pack greedily, starting a new day whenever the next package would overflow: 1+2+3+4+5+6+7 | 8+9+10, 2 days. Within 5, so 32 works and anything bigger is unnecessary: hi = 32.
Capacity 32 needs 2 days, feasible.
Range 10 to 32, probe capacity 21. Pack greedily, starting a new day whenever the next package would overflow: 1+2+3+4+5+6 | 7+8 | 9+10, 3 days. Within 5, so 21 works and anything bigger is unnecessary: hi = 21.
Capacity 21 needs 3 days, feasible.
Range 10 to 21, probe capacity 15. Pack greedily, starting a new day whenever the next package would overflow: 1+2+3+4+5 | 6+7 | 8 | 9 | 10, 5 days. Within 5, so 15 works and anything bigger is unnecessary: hi = 15.
Capacity 15 needs 5 days, feasible.
Range 10 to 15, probe capacity 12. Pack greedily, starting a new day whenever the next package would overflow: 1+2+3+4 | 5+6 | 7 | 8 | 9 | 10, 6 days. More than 5, so 12 is too small and so is everything below it: lo = 13.
Capacity 12 needs 6 days, infeasible.
Range 13 to 15, probe capacity 14. Pack greedily, starting a new day whenever the next package would overflow: 1+2+3+4 | 5+6 | 7 | 8 | 9 | 10, 6 days. More than 5, so 14 is too small and so is everything below it: lo = 15.
Capacity 14 needs 6 days, infeasible.
Least capacity: 15, found with 5 probes over a range of 46 candidates. Each probe is one O(n) greedy check, so the search costs O(n log(sum)).
Least capacity 15 after 5 probes.
Write it yourself
Define leastCapacity(values, limit) and return the smallest ship capacity that moves every package within the day limit, in order. It runs in your browser against this lesson's own 2 examples.
// Guessing a capacity is easy to check: the answers are sorted by feasibility, so binary search the capacity.function leastCapacity(values, limit) { return 0;}
Remember
- Look for a yes/no question that is monotonic in x; then the answer space is sorted and can be halved.
- Feasible probe: the answer is at most mid, so hi = mid. Infeasible: lo = mid + 1.
- The bounds come from the problem: heaviest item to total weight, speed 1 to the largest pile.
Topics covered
Related
Where this is used
NetworkingBIC TCP congestion control
BIC, the default TCP congestion control in Linux kernels 2.6.8 through 2.6.18, keeps the window size that last caused packet loss and the window it knows is safe, then aims the next window at the midpoint of the two, with a cap on how far a single step may jump. Sending at a window is the feasibility probe and losing packets is the no, so the window closes on the usable bandwidth in a few round trips instead of growing by one packet per round trip.
CompilersLLVM's -opt-bisect-limit
When an optimised build miscompiles a program, -opt-bisect-limit=n makes LLVM run only the first n optimisation passes and skip everything above that index. 'Is the program still correct at limit n' flips from yes to no at one value, so you bisect the limit rather than switching passes off one at a time, and a pipeline of thousands of pass invocations narrows to the guilty one in around a dozen builds.
OperationsRFC 2544 throughput benchmarking
RFC 2544 is the benchmarking procedure for a switch or router's throughput, which RFC 1242 defines as the highest frame rate the box forwards with zero loss, and every candidate rate costs a full timed trial run on real hardware. The RFC leaves the search itself to the tester, so testers treat 'nothing dropped at rate r' as monotonic and bisect the rate between zero and line rate, which turns a measurement that would need hundreds of trials into roughly a dozen.
OptimisationBracketed root finding in numerical libraries
scipy.optimize.bisect, and the safety net inside scipy.optimize.brentq, are this same search over the real numbers: you hand in an interval where f changes sign, and the routine halves it without ever enumerating candidate values. The predicate is 'is f negative at this point', and the sign change guarantees at least one flip inside the bracket, which is all halving needs to home in on a root. Bisection is the slowest step-for-step and the only one that cannot diverge, which is why the fast methods fall back to it.
Why it works this way
How do you know the answers are sorted when nothing sorted them?
You prove it about the problem, not by looking at the data: if x works, must x + 1 also work? A bigger hold is never worse than a smaller one, so ship capacity passes the test. Questions phrased with 'exactly' usually fail it - 'do these packages take exactly 5 days' is false at small capacities, true across a band of them, then false again once a bigger hold finishes sooner. That predicate flips twice, and halving on it can discard the band that holds the answer and still return a plausible looking number. Note too that the weights array is never sorted; the sorted thing is the range of capacities, which exists only in lo and hi.
Why while (lo < hi) and return lo, with no not-found case
Plain binary search can fail, because the target may simply not be in the array. This search cannot fail: the bounds are picked so that hi is definitely feasible and everything below lo is definitely not, which means the answer is somewhere in [lo, hi] before the loop even starts. So the loop squeezes the two ends together instead of testing for a hit, and whatever they meet on is the answer. The flip side is that a bad upper bound fails silently - if hi were too small to be feasible you still get a number back, and it is just wrong.
Searching for the largest feasible value needs a different midpoint
The code here finds the smallest x that works, and that pairs floor division with hi = mid. Turn the question around to the largest x that works and you pair lo = mid with a midpoint that rounds up: lo + (hi - lo + 1) / 2. Crossing the two is the classic infinite loop - with lo and hi adjacent a floored mid equals lo, so lo = mid changes nothing and the loop spins forever. The snippet above writes (lo + hi) / 2 to stay short, but hi here is a sum or a limit from the problem rather than an array index and can sit anywhere in the integer range, so real code should use lo + (hi - lo) / 2.
The log is over the range of values, not over n
Every probe costs a full pass over the data, and the number of probes is log2 of the width of the bound range - about 30 even when the weights sum into the billions. Doubling the number of packages doubles the running time, while doubling every weight adds one probe. That is also why the feasibility check has to be exact and not merely close: daysNeeded packs greedily, and the search is correct only because that greedy packing provably uses the fewest days. An approximate check still converges, just on the wrong number.