Run it
The probe table: five probes over a range of forty-six candidates.
Monotonicity is what licenses the search, so check it rather than assume it.
The same shape on a different question, to show it is a pattern and not a trick.
Recognising it
The tell is a question of the form "what is the smallest X such that something is possible" — smallest capacity, minimum speed, fewest days, largest minimum distance. There is no sorted array in the input, which is why the shape gets missed.
What is sorted is the answer space. If you can write a function feasible(x) that is False for every x below the answer and True for every x at or above it, then the sequence feasible(lo) ... feasible(hi) is sorted — and finding where it flips is exactly binary search.
The three things to establish before writing the loop
The predicate. Here, "can capacity c deliver everything in D days?" Greedily load until the next package would overflow, then start a new day. One pass, O(n), and greedy is optimal for it because leaving room spare can never reduce the day count.
Monotonicity. A bigger ship cannot need more days. State it — this is the step that makes the search valid, and an interviewer will ask why you are allowed to binary search something with no array in it.
The bounds. lo = max(weights), because a package must fit in one trip. hi = sum(weights), because that always finishes in one day. Getting the low bound wrong — starting at 1, or at 0 — produces a search over capacities that can never work, and the loop returns an infeasible answer rather than looping forever, which is worse.
Cost, and the shape of it
O(n log(sum − max)): a logarithmic number of probes, each costing a linear pass. Note that the log is over the magnitude of the answer range rather than the size of the input, which is unusual and worth saying — it means the complexity depends on the numbers, not just on how many there are.
The editor below prints the probe table. Ten packages give a range of 46 candidate capacities and the search settles it in five probes.
The same shape, four other questions
Koko eating bananas — smallest eating speed to finish in H hours. Identical, with ceil(pile / speed) as the per-pile cost.
Split an array into k subarrays minimising the largest sum. The predicate is "can we do it with all parts at most m", and it is the same greedy pass.
Aggressive cows / maximum minimum distance — place k items as far apart as possible. The monotonicity flips direction: large distances are infeasible, so you search for the last True instead of the first.
The square root of an integer, or any inverse of a monotonic function. Once the pattern is visible, "is there a monotonic predicate here?" becomes a routine question to ask of any minimisation problem.
What to say out loud
I binary search the answer rather than an array. The predicate is 'can this capacity finish in D days', which I can check in one pass, and it is monotonic - if a capacity works, anything bigger works. So the feasible capacities are a suffix, and I search for the first one. Bounds are max weight to total weight, so it is O(n log sum).
Edge cases to raise
Volunteering these is most of what separates a correct answer from a good one.
Verify the monotonicity. If the predicate flips more than once, binary search returns a boundary that means nothing. Printing it either side of the answer is cheap insurance.
The bounds must bracket the answer. Too low and the search can return an infeasible value; too high only costs a probe or two. When in doubt, err high.
The log is over the magnitude of the answer range, not the input length - so the complexity depends on the size of the numbers. Worth stating, because it is unusual.
The follow-ups interviewers ask
"Koko eating bananas." Identical: smallest speed such that the total hours fit, with ceil(pile / speed) per pile. If you can see that these are the same question, you have the pattern.
"Split an array into k parts minimising the largest sum." The predicate is 'can it be done with every part at most m', checked greedily in one pass. Same search, same monotonicity.
"Maximise the minimum distance when placing k items." The monotonicity reverses - large distances are infeasible - so you search for the last feasible value instead of the first. Recognising that the direction flips is the test.
Common wrong answers
"There is nothing sorted, so binary search does not apply." The answer space is sorted, even when the input is not. That reframing is the entire question.
"Start the range at 1." Sometimes harmless and sometimes not. The lower bound must be feasible-or-below by construction; for capacity that is max(weights), because a single package has to fit.
"Check feasibility by trying all arrangements." The greedy pass is O(n) and optimal here. Searching arrangements makes each probe exponential and throws the whole benefit away.
Recap in one screen
- The thing being searched is a range of answers, not the input.
- Each probe costs a full O(n) pass - the feasibility check.
- The predicate flips exactly once, which is what makes it searchable.
- Worth trying: Set lo = 1 instead of max(weights) and look at the answer. It is still correct here - work out why, and then find an input where it would not be.
- Worth trying: Change the question to "the largest minimum gap when placing k items". The monotonicity reverses, so you search for the last feasible value instead of the first.