Clinic #33: Koko Eating Bananas

Pattern: Binary search on the answer · LC 875

Is the Hinglish foundations board for sorting and searching. Its fifth panel is this clinic in one picture: a row of candidate speeds, crosses on the slow ones, ticks on the fast ones, and one border between them that binary search finds.

Before you start. Sorting & Searching showed binary search on a sorted list: look at the middle item, throw away the half that cannot hold what you want, repeat, so a million items takes about twenty looks instead of a million. Everything in this clinic is that same move, with one change: the sorted list you search is not in the input at all.

The idea in 30 seconds

The answer here is a machine size, and the machine sizes are not in the input. Binary searching the bags looks in the wrong list.
Dividing the total by the hours gives a floor, not the answer, because a load holds only one bag, so each bag’s half-full last load wastes space the average counts as used.
“Does this size fit?” is a predicate, a yes/no test on one candidate. It is monotone: once a size fits, every bigger size fits.
A monotone predicate turns the candidates into a sorted row of no’s then yes’s. The answer is the boundary between them.
Binary search on the answer halves that row, computing each entry on demand: about thirty tests for a billion candidates.
On a yes, keep the middle (it might be the answer); on a no, drop it. Stop when one candidate is left.

Read the story · Skip to the numbers