There are n piles of bananas, given in a list called piles. Koko eats at a speed of k bananas per hour. Each hour, she picks one pile and eats up to k bananas from it. If that pile has fewer than k left, she finishes it and rests for the rest of the hour. She never moves on to a second pile within the same hour.
She has h hours. Return the smallest whole-number speed k that lets her finish every pile within h hours.
There is no sorted list here, and nothing obvious to search. But turn the question around. Instead of "what is the best speed?", ask a simpler yes/no question:
At speed k, can she finish in time?
That is easy to answer. Work out the hours for each pile, add them up, and compare with h. A pile of size p at speed k takes p \div k hours, rounded up, because a part-finished pile still costs a whole hour:
\text{hours for a pile} = \left\lceil \frac{p}{k} \right\rceil
The symbols \lceil \ \rceil mean ceiling, which means "round up to the next whole number". \lceil 10 / 3 \rceil = \lceil 3.33 \rceil = 4.
Now look at how the yes/no answer changes as the speed goes up.
speed k: 1 2 3 4 5 6 ...in time? no no no yes yes yes ... ↑ the answer
Once a speed is fast enough, every faster speed is also fast enough. The answers go "no, no, no", then "yes, yes, yes", and never switch back. That is exactly the monotonic yes/no shape from the end of 4.11.1. So we can binary search the speed itself.
This move is called binary search on the answer. Check three things before you use it.
The answer is a number inside a range you know.
"Does this value work?" is easy to check.
If a value works, every bigger value works too (or every smaller one, depending on the problem).
What is the slowest speed worth trying? 1 banana per hour.
What is the fastest speed worth trying? The size of the biggest pile. At that speed, every pile takes exactly 1 hour. Going any faster cannot help, because she can only eat from one pile per hour anyway.
(1) How many hours does speed k need? Add up the rounded-up hours for every pile. (p + k - 1) // k is how you round a division up using only whole numbers. This is how it works.
// divides and rounds down. To round up instead, add just enough to push any leftover past the next whole number. k - 1 is exactly enough.
If p divides exactly by k, adding k - 1 is not enough to reach the next multiple, so the answer does not change. For p = 6, k = 3: (6 + 2) // 3 = 8 // 3 = 2. ✓
If there is any leftover, adding k - 1 pushes it over. For p = 7, k = 3: (7 + 2) // 3 = 9 // 3 = 3. ✓
Why not math.ceil(p / k)? Because p / k makes a decimal first. Very large numbers cannot always be stored exactly as decimals, so the rounding can come out wrong. Whole-number arithmetic has no such limit. In TypeScript, Math.ceil(p / k) is fine here, because the numbers in this problem are small enough to be exact.
(2) The range of speeds, from 1 to the biggest pile.
(3) Shape B from 4.11.1: find a boundary. We are not looking for one exact value. We are looking for the point where "too slow" turns into "fast enough". So the loop runs while low < high, and it ends when the range has shrunk to a single speed.
(4) Fast enough at mid. Then mid might be the answer, or something slower might also work. So we keep mid in the range with high = mid. Using mid - 1 here would throw away a speed that could be the answer.
(5) Too slow at mid. Then mid and every slower speed are useless. Move low past it.
(6) low and high have met on the slowest speed that works.
Take piles = [3, 6, 7, 11] and h = 8. The range is 1 to 11.
Step
low
high
mid
Hours at mid
Within 8?
Action
1
1
11
6
1 + 1 + 2 + 2 = 6
yes
high = 6
2
1
6
3
1 + 2 + 3 + 4 = 10
no
low = 4
3
4
6
5
1 + 2 + 2 + 3 = 8
yes
high = 5
4
4
5
4
1 + 2 + 2 + 3 = 8
yes
high = 4
end
4
4
return 4
Check the hours in step 2 by hand. At speed 3: the pile of 3 takes 1 hour, the pile of 6 takes 2, the pile of 7 takes \lceil 7/3 \rceil = 3, and the pile of 11 takes \lceil 11/3 \rceil = 4. That is 10 hours, more than 8, so speed 3 is too slow.
Let n be the number of piles and M the biggest pile.
Time. The binary search runs over the range 1 to M, so it takes about \log_2 M steps. For M = one billion, that is about 30 steps. Each step calls hours_needed, which walks all n piles. So the total is O(n \log M).
Notice that the \log is over the size of the values, not the number of piles. That is typical of binary search on the answer, and it is why the method stays cheap even when the range of answers is enormous.
Each of these is the same ten lines with a different "does this value work?" check.
Capacity to Ship Packages Within D Days. Find the smallest ship capacity that delivers all packages, in order, within D days. The check walks the packages, starting a new day whenever the next one will not fit. The range runs from the heaviest package to the total weight.
Split Array Largest Sum. The same problem as shipping, worded as cutting a list into parts.
Find the Smallest Divisor Given a Threshold. The check is this page's rounded-up sum, almost exactly.
Minimum Number of Days to Make m Bouquets. The check walks the flowers, counting runs of neighbours that have bloomed.
How to recognise the family: the problem says minimise the maximum, maximise the minimum, or find the smallest value such that…. That wording almost always means binary search on the answer.
"Why can you binary search when nothing is sorted?" Because the yes/no answers over the speeds are monotonic. State the three conditions.
"What is your range, and why?" 1 to the biggest pile. Faster than the biggest pile gains nothing, because she eats from only one pile per hour.
"Why high = mid and not mid - 1?" A speed that works might be the answer, so it stays in the range.
"Why whole-number ceiling division?" Decimals can lose accuracy on large numbers. (p + k - 1) // k is always exact.
"What is the complexity?"O(n \log M). Point out that the \log is over the values.
One thing to volunteer: name the technique and state the monotonic property in one sentence. "If speed k finishes in time, every faster speed does too, so I can binary search the speed."