Koko Eating Bananas
Binary search the ANSWER (speed), not the array
There's no array of speeds to search — but speed behaves monotonically: a faster k always needs fewer-or-equal hours, never more. That monotonic relationship is exactly what binary search needs, so it works the same as searching a sorted array, just with 'is this speed fast enough?' standing in for 'is this the target?'.
Details
Animated on: piles = [3,6,7,11], h = 8 — find the minimum constant eating speed k so all piles finish within h hours.
Problem:Koko Eating BananasMedium
Pattern:Binary Search on Answer
Binary search the ANSWER (speed), not the array
step 1 / 5
piles=[3,6,7,11], h=8 hours available. Binary search the SPEED k (1..11): higher k always means fewer or equal hours needed, so hours-needed is monotonic in k — perfect for binary search.
1FUNCTION minEatingSpeed(piles, h):2 low = 1, high = the largest pile3 WHILE low <= high:4 mid = (low + high) / 2, rounded down5 hours = for each pile, add up ceil(pile / mid)6 IF hours <= h:7 ans = mid; high = mid - 1 (try slower)8 ELSE:9 low = mid + 1 (too slow, go faster)10 RETURN ans
← / → step · space play · Home restart
Every step in words
Show all 5 steps
- piles=[3,6,7,11], h=8 hours available. Binary search the SPEED k (1..11): higher k always means fewer or equal hours needed, so hours-needed is monotonic in k — perfect for binary search.
- k=6: needs 6 hours (<= 8). Feasible — remember it and try a SLOWER speed to see if it still works. high = 5.
- k=3: needs 10 hours (> 8). Too slow — need a faster speed. low = 4.
- k=4: needs 8 hours (<= 8). Feasible — remember it and try a SLOWER speed to see if it still works. high = 3.
- Search exhausted. The minimum speed that finishes within 8 hours is k=4.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.