Binary search on the answer, when nothing is sorted

The questions#

• The smallest ship that gets every package away in five days.
• Sharing books between students so the unluckiest reads as little as possible.
• The slowest Koko can eat and still finish the bananas in time.
• The fewest painters, the smallest divisor, the closest the cows can be placed.

None of these mention a sorted list. All of them are binary search.

What is being searched#

Not the input. The answer.

Every one of these asks for the smallest (or largest) value that still works. The candidate answers form a range, and if you write down whether each one works, the range always looks like this:

  no  no  no  no  YES YES YES YES
                   ^
             the answer

A run of no followed by a run of yes is exactly the shape binary search handles. You do not need the input sorted; you need the answers ordered, and here they are, for a reason.

The two things you must be able to say#

Before writing a line, say both of these out loud about your problem.

1. Given a guess, can I check it in one pass?

For the ship: walk the packages, start a new day when the next one will not fit, count the days. One pass, no cleverness.

If checking a guess is itself hard, this technique does not apply.

2. If a guess works, does every larger one work too?

For the ship: a bigger boat cannot need more days. So yes.

That property is monotonicity, and it is the whole justification. Without it the answers are scattered and halving the range proves nothing. This is the step people skip, and it is the step that decides whether the approach is correct or merely usually right.

The shape#

low, high = the smallest and largest answers worth considering
while low < high:
    mid = (low + high) / 2
    if works(mid): high = mid        # mid is a candidate, keep it
    else:          low = mid + 1     # mid is not, discard it
return low

Two details carry all the weight.

high = mid, not mid - 1. mid worked, so it might be the smallest thing that works. Throwing it away steps past the answer.

The loop is low < high, not low <= high. With high = mid the range always shrinks, and the loop ends with low == high, which is the answer. Using <= with high = mid loops for ever, and that is the bug you will actually write.

Looking for the largest value that works flips it: low = mid for a success, and mid = (low + high + 1) / 2 so the middle rounds up. Round down there and it loops for ever too.

Choosing the ends#

Get these wrong and the search is either incorrect or slow.

• The low end is the smallest value that could conceivably work. For the ship that is the heaviest single package, because nothing smaller ever fits it.
• The high end is something that certainly works. For the ship that is the total weight: one day, everything aboard.

A high end that does not work breaks the search. When unsure, pick something obviously large: the cost is one extra step per doubling, which is nothing.

What it costs#

log(range) guesses, each costing one pass. For the ship that is about 25 guesses over a range of 25 million, each a walk of the packages. The range being enormous barely matters, which is the whole point.

Recognising it#

The giveaway is a question asking for a minimum maximum or a maximum minimum: the smallest largest load, the largest smallest distance. That phrasing almost always means this technique, and once you hear it the rest is filling in works().

Practice in order#

1. Ship packages in D days, where the mapping is most visible.
2. Allocate minimum pages, which is the same problem with students and books, and worth solving deliberately to feel that it is the same.
3. Koko eating bananas, where the check involves a rounding-up division that is easy to get wrong.