Binary search on the answer

45 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Koko has four piles of bananas: 3, 6, 7, 11. She eats at a fixed speed of k bananas per hour, finishing at most one pile per hour (if a pile has fewer than k she still spends the hour). The guards return in 8 hours. What is the slowest speed that still finishes every pile in time?

By hand: at speed 1 the piles take 3 + 6 + 7 + 11 = 27 hours, too slow. Speed 2: 2 + 3 + 4 + 6 = 15 hours. Speed 3: 1 + 2 + 3 + 4 = 10. Speed 4: 1 + 2 + 2 + 3 = 8. That fits, and 3 did not, so the answer is 4. You tried every speed from 1 up, and each try walked all the piles. If the biggest pile held a billion bananas, the answer could be around a billion, and you would do a billion tries.

Notice the pattern of the tries: too slow, too slow, too slow, fits, fits, fits, … Once a speed works, every faster speed works. That is a yes/no condition that is false and then true, and we already know how to find such a boundary quickly.

Build the structure, one piece at a time

Piece 1: a checker. Write feasible(k): hours needed at speed k is the sum over piles of ⌈pile / k⌉; return whether that is ≤ 8. This is a straight walk over the piles.

Piece 2: a range of possible answers. The slowest sensible speed is 1 and the fastest useful speed is the biggest pile, 11, since anything faster changes nothing. So lo = 1, hi = 11.

Piece 3: binary search the boundary. Test the middle speed. If it is feasible, the answer is mid or slower: hi = mid. If not, the answer is faster: lo = mid + 1. Stop when lo = hi.

Four checks instead of four tries here, but for a billion-banana pile it is about thirty checks instead of a billion.

Why it is correct

The whole method rests on one fact: feasible(k) is monotone. If speed k finishes in time, speed k + 1 does too, because each pile takes the same or fewer hours.

⌈p / (k + 1)⌉ ≤ ⌈p / k⌉ for every pile p, so hours(k + 1) ≤ hours(k)

Given monotonicity, the invariant is the boundary-search invariant: feasible(lo − 1) is false (or lo is the minimum speed) and feasible(hi) is true. Moving lo past an infeasible mid and hi onto a feasible mid keeps both facts, the range shrinks every step, and lo = hi is the smallest feasible speed.

The checker must be exact and greedy-simple. For "minimise the largest sum when splitting an array into m parts", the checker is: walk the array, start a new part whenever adding the next element would exceed the guessed limit, and count the parts. That greedy count is the fewest parts possible for that limit, so the check is exact.

Why it is fast

The number of checks is about log₂ of the size of the answer range, and each check walks the n piles once.

time = O(n × log₂(hi − lo)) = O(n log(range))

For 1000 piles and a range of a billion that is 1000 × 30 = 30 000 steps, instead of 1000 × a billion.

How to recognise it in an interview

The cues are "minimum speed / capacity / time such that", "minimise the maximum", "maximise the minimum", "smallest x that makes it possible". Whenever checking a given answer is easy but computing the answer directly is not, ask whether the check is monotone. Say: "I can verify a candidate in O(n) and feasibility is monotone, so I binary search over the answer."

Koko Eating Bananas is the example above. Capacity To Ship Packages Within D Days guesses a ship capacity and counts days greedily. Split Array Largest Sum guesses the largest allowed sum and counts parts. Swim in Rising Water guesses a water level and checks reachability with a flood fill, which shows the checker can be a graph search.

02The idea in one line

Guess an answer, check feasibility greedily, tighten the range.

Reach for it when: Split array largest sum, Koko bananas, ship capacity, minimize max / maximize min.

Cost: O(n log range) time.

03The walk-through, step by step

The video works one example: Koko Eating Bananas piles [3,6,7,11], h=8. These are its captions in order, so you can follow without the video or check a step you missed.

1. Guess a speed k, check feasibility, then halve the k range
2. k = 6: hours = 1 + 1 + 2 + 2 = 6 ≤ 8
3. Feasible: try slower, hi = 6
4. k = 3: hours = 1 + 2 + 3 + 4 = 10 > 8
5. Too slow: need faster, lo = 4
6. k = 5: hours = 1 + 2 + 2 + 3 = 8 ≤ 8
7. Feasible: try slower, hi = 5
8. k = 4: hours = 1 + 2 + 2 + 3 = 8 ≤ 8
9. Feasible: try slower, hi = 4
10. lo == hi: the minimum feasible speed is 4
11. feasible(k) is monotone, so the answer is a boundary: O(n log range)

04Asked at Google

13 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Binary Search: Classic binary search, First true (predicate boundary), Rotated / mountain search, Partition two sorted arrays.