What binary search on the answer is
Koko has piles of bananas —
[3, 6, 7, 11] — and 8 hours. Each hour she picks one pile and eats up to s bananas from it (a small pile still uses the whole hour). What's the slowest speed s that finishes everything in time?There is no array to search here. But look at the candidates: at speed 1 she needs
3 + 6 + 7 + 11 = 27 hours — hopeless. At speed 11 she needs 4 hours — easy. And here is the key property: if a speed works, every faster speed also works. So the candidates line up astoo slow, too slow, …, too slow | works, works, …, worksfeasibility flips exactly once. From the Binary Search lesson, that's precisely the shape the boundary template searches — the candidates behave like a sorted space even though nothing is stored in an array. Binary search on the answer is exactly that: binary-search the candidate answers, replacing "compare
arr[mid] to the target" with "is mid feasible?" — here, does eating at speed mid finish within 8 hours?Quick check
What property of the candidate speeds makes binary search legal here?
Answer it in the interactive lesson to keep your progress.
How it works, step by step
The pieces
- Bounds. The slowest candidate is
1; the fastest useful one is the biggest pile,11(faster than that changes nothing — one pile per hour is the ceiling). - The feasibility check. At speed
s, a pile ofpbananas takesceil(p / s)hours (a 7-pile at speed 4 takes 2 hours — the leftover hour is still an hour). Total: - The boundary walk. From the Binary Search lesson, verbatim: a feasible
midmight BE the answer, so it stays (hi = mid); an infeasiblemidis ruled out (lo = mid + 1).
Trace it — piles [3, 6, 7, 11], h = 8
| try speed | hours = ceil sums | verdict | new range |
|---|---|---|---|
| 6 | 1+1+2+2 = 6 | fits (≤ 8) | 1..6 |
| 3 | 1+2+3+4 = 10 | too slow | 4..6 |
| 5 | 1+2+2+3 = 8 | fits | 4..5 |
| 4 | 1+2+2+3 = 8 | fits | 4..4 |
lo meets hi at 4 — four feasibility checks instead of eleven.In the animation, remember what the row of numbers is: not data, but candidate speeds — watch each tried speed show its hours arithmetic in the caption, and the infeasible side of the row fade away for good. In JavaScript:
This section has a step-by-step animation in the interactive lesson.
function minEatingSpeed(piles, h) {
let lo = 1;
let hi = Math.max(...piles);
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
const hours = piles.reduce((t, p) => t + Math.ceil(p / mid), 0);
if (hours <= h) hi = mid; // feasible — might be the answer
else lo = mid + 1; // too slow — ruled out
}
return lo;
}
console.log(minEatingSpeed([3, 6, 7, 11], 8)); // 4Quick check
Range is speeds 4..6 and mid = 5 turns out FEASIBLE. Predict the next range.
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
- Feasibility must be monotonic. If 'works' can flip back to 'fails' as the candidate grows, there is no single boundary and the halving logic silently returns nonsense. Before writing any code, say the sentence: "if X works, does every bigger X work?" If you can't say yes, this pattern doesn't apply.
- Keep the feasible mid. The whole point is finding the smallest workable answer, so a workable
midmust stay in range:hi = mid, nevermid - 1. This is the same boundary rule from the Binary Search lesson — and the same infinite-loop warning: pairhi = midwithlo = mid + 1, or the window can stop shrinking. - Get the bounds right.
lotoo high orhitoo low and the true answer sits outside the search — the walk then confidently returns a wrong boundary. When minimizing a shipping capacity, for example,lomust be the largest single item (anything less can't ship it at all) andhithe total sum. - The check is the cost. Each probe runs a full
O(n)pass. That's fine forlog(max)probes — but resist stuffing an expensiveO(n²)verifier inside the loop.
Quick check
A problem's check: "does the team finish if we hire exactly k people?" — too FEW fails, but too MANY also fails (coordination overhead). Can you binary-search k?
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, the cost is checks × cost-per-check:
| Approach (n piles, max pile m) | Time | Why |
|---|---|---|
| test every speed 1…m | O(n · m) | a full check per candidate |
| binary search the speeds | O(n log m) | ~log m checks, each O(n) |
Space is
O(1) — two bounds and a counter.Key takeaways:
- No array needed — the candidates are the search space, and monotonic feasibility is the "sortedness".
- Feasible mid stays (
hi = mid); infeasible is ruled out (lo = mid + 1).lomeetshiat the boundary. - Always sanity-check the monotone sentence and the two bounds before coding.
- Cost =
log(range)× one feasibility pass.
The same template answers a family of classics, each its own lesson later (no need to know them yet): ship packages within D days (minimum capacity — this topic's Level-2 challenge), split array largest sum (minimize the biggest chunk), and minimum days for m bouquets (search the days). The second animation replays first bad version — the boundary skeleton all of these stand on. Next up in order: Bit Manipulation — using the individual bits of a number as a tiny, fast set.