Binary Search on Answer Explained: Koko Eating Bananas

Imagine you are Koko, and you love bananas. You are looking at a line of four piles with sizes $[3,6,7,11]$ bananas, and the guards will return in $h=8$ hours. You can choose to eat at a constant speed of $k$ bananas per hour. If a pile has fewer than $k$ bananas, you finish it in that hour and stop eating for the rest of that hour. If you eat at a speed of $k=1$, you will take $3+6+7+11=27$ hours, which vastly exceeds your 8-hour limit. If you eat at a blazing speed of $k=11$, you finish each pile in 1 hour, taking 4 total hours—well under the limit, but you waste a lot of energy chewing so fast.

To find the absolute minimum integer speed $k$ that still lets you finish in $\le 8$ hours, your first instinct might be to test every single speed from 1 up to the maximum pile size of 11. You would simulate speed 1, then speed 2, then speed 3, and so on until you hit $k=4$, which takes exactly 8 hours. While this linear scan works for tiny inputs, what happens if the guards give you piles reaching $10^9$ bananas and $h=10^9$ hours? A linear search would perform a billion iterations, timing out instantly.

We need a way to rule out entire blocks of speeds at once rather than checking them one by one. Because the total hours needed decrease monotonically as our speed $k$ increases, we can leverage the hidden order of the solution space instead of stumbling through it blindly.

When Koko faces piles = [3, 6, 7, 11] and h = 8, she doesn't need to test every single speed from 1 to 11 one by one. Instead, we can think of her eating speed $k$ as a range of candidate values. The minimum possible speed is 1 (she eats at least one banana per hour), and the maximum possible speed is the largest pile, which is 11 (eating faster than the largest pile yields no time-saving benefit since she can only eat from one pile per hour).

This range $[1,11]$ has a powerful property: monotonicity. If Koko can successfully finish all bananas at speed $k=4$, she can also finish them at any speed greater than 4 (like $5,6,11$). Conversely, if she fails at $k=3$, she will fail at any slower speed. Whenever a search space is sorted and monotonic, linear scanning is unnecessary—we can use binary search.

To evaluate any candidate speed $k$, we simulate her eating process across our specific piles: $[3,6,7,11]$. For each pile of size $p$, the hours required at speed $k$ is given by the ceiling division $\lceil p/k\rceil$. Summing these up gives the total hours needed for that speed.

Having established that speed $k$ forms a clean monotonic range, we now trace the binary search procedure end-to-end on our locked working example. We are given piles $piles=[3,6,7,11]$ and a time limit $h=8$ hours. Our goal is to find the minimum integer $k$ bananas per hour that allows Koko to finish all bananas within 8 hours.

- $piles=[3,6,7,11]$ (four piles of sizes 3, 6, 7, and 11)
- $h=8$ hours
- Search bounds: $lo=1$ (minimum possible speed) and $hi=\max (piles)=11$ (maximum possible speed, since she can eat at most one pile per hour).

We iteratively compute the midpoint $mid=\lfloor (lo+hi)/2\rfloor$, calculate the total hours required at speed $mid$, and adjust our bounds.

- $lo=1,hi=11⟹mid=6$.
- Compute hours needed at $k=6$: $\lceil 3/6\rceil +\lceil 6/6\rceil +\lceil 7/6\rceil +\lceil 11/6\rceil =1+1+2+2=6$ hours.
- Since $6\le 8$, Koko finishes in time! But can she go slower? We record 6 as a valid answer and try a smaller speed by setting $hi=mid=6$.

- $lo=1,hi=6⟹mid=3$.
- Compute hours needed at $k=3$: $\lceil 3/3\rceil +\lceil 6/3\rceil +\lceil 7/3\rceil +\lceil 11/3\rceil =1+2+3+4=10$ hours.
- Since $10>8$, 3 is too slow. Koko needs a higher speed, so we adjust $lo=mid+1=4$.

- $lo=4,hi=6⟹mid=5$.
- Compute hours needed at $k=5$: $\lceil 3/5\rceil +\lceil 6/5\rceil +\lceil 7/5\rceil +\lceil 11/5\rceil =1+2+2+3=8$ hours.
- Since $8\le 8$, 5 is valid! We record 5 and try a smaller speed by setting $hi=mid=5$.

- $lo=4,hi=5⟹mid=4$.
- Compute hours needed at $k=4$: $\lceil 3/4\rceil +\lceil 6/4\rceil +\lceil 7/4\rceil +\text{Pclass}\dots$ wait, let us trace exact integer math: $1+2+2+3=8$ hours? Let us check: $\lceil 3/4\rceil =1$, $\lceil 6/4\rceil =2$, $\lceil 7/4\rceil =2$, $\lceil 11/4\rceil =3$. Sum = $1+2+2+3=8$ hours.
- Since $8\le 8$, 4 is valid! We set $hi=mid=4$.

- Now $lo=4$ and $hi=4$. The search space collapses.

The minimum speed that satisfies $h=8$ is $k=4$. Notice how testing speeds eliminated half the remaining search space at each step.

Try this: Given piles = [3, 6, 7, 11] and h = 8, suppose we evaluate speed k = 2. Exactly how many total hours does Koko require, and why does this rule out k = 2?

Now that you have traced the standard execution for piles = [3, 6, 7, 11] and h = 8 where the optimal speed is $k=4$, let us test your grip on the search dynamics. Suppose we modify the target hours constraint to be much stricter: $h=4$ hours for the exact same pile sizes [3, 6, 7, 11].

Recall that the search bounds are initially $\text{lo}=1$ and $\text{hi}=11$, and our hour-calculation function uses the ceiling division formula $\sum \lceil \frac{\text{pile}}{k}\rceil$. Think about what happens at the very first midpoint, and whether Koko can finish all piles within 4 hours at that speed.

Given piles = [3, 6, 7, 11] and a strict time limit $h=4$, evaluate the first iteration of the binary search:

1. What is the initial midpoint speed $k$, and how many hours does Koko require at this speed?
2. Based on whether this hour total is $\le 4$ or $>4$, which pointer (lo or hi) will move, and what is the new search interval for the next step?

Take a moment to write down or mentally trace your calculations before checking how the monotonicity invariant guides the update.

Try this: piles = [3, 6, 7, 11], h = 4
lo = 1, hi = 11
mid = (1 + 11) // 2 # Evaluate hours needed here

We started with Koko facing piles $[3,6,7,11]$ and $h=8$ hours, where brute-force iteration through speeds $k=1,2,3,\dots ,11$ was too slow. By realizing that speed $k$ has a monotonic property—if Koko can finish at speed 4, she can also finish at speed 5 or 11, but fails at 3—we transformed an unordered optimization problem into a binary search over a sorted range of answers.

This exact pattern appears whenever a problem asks for the minimum valid maximum or maximum valid minimum threshold, and checking a candidate value is fast. Consider a shipping company needing to transport packages of weights within $d$ days. Instead of guessing days, you guess the maximum daily weight capacity $k$, and use a greedy pass to check if the fleet can finish within $d$ days.

Just like Koko's piles, if capacity $k$ works, any higher capacity also works, allowing us to shrink the upper bound (hi = mid). If capacity $k$ is too small, we must increase the lower bound (lo = mid + 1). Whenever you see a problem asking for the "minimum capacity", "smallest speed", or "earliest time" subject to a feasibility check, pause and ask: Can I binary search the answer?