Binary Search on the Answer: Solving 'Koko Eating Bananas'

Koko Eating Bananas is a very good binary‑search problem because there is no sorted array to search through in the usual sense. That is exactly what makes it useful. The question is not "where is the target value?" but:

• what is the smallest eating speed that still gets the job done in time?

That puts us into one of the most reusable binary‑search variants:

• binary search on the answer

The Brute‑Force Version is Easy to See

If Koko can eat at any integer speed from 1 up to the size of the largest pile, then one obvious answer is:

• try speed 1
• try speed 2
• try speed 3
• keep going until one works

That does eventually solve the problem.

The reason it is not the answer we want is that it checks far too many speeds one by one, even though the question has a very orderly structure once we phrase it properly.

The Question That Unlocks Binary Search

The useful helper is:

• if Koko eats at speed k, can she finish within h hours?

That is a yes‑or‑no question. Better still, it is monotonic:

• if speed k works, every speed bigger than k also works
• if speed k does not work, every speed smaller than k also does not work

That monotonic boundary is exactly what binary search needs.

We are not searching through the piles. We are searching through the possible speeds.

A Practical TypeScript Solution

const canFinishAtSpeed = (  piles: number[],  maxHours: number,  speed: number): boolean => {  let hoursNeeded = 0;  for (const pile of piles) {    hoursNeeded += Math.ceil(pile / speed);    if (hoursNeeded > maxHours) {      return false;    }  }  return true;};export const minEatingSpeed = (  piles: number[],  hours: number): number => {  let left = 1;  let right = Math.max(...piles);  while (left < right) {    const middle = Math.floor((left + right) / 2);    if (canFinishAtSpeed(piles, hours, middle)) {      right = middle;    } else {      left = middle + 1;    }  }  return left;};

Why Math.max(...piles) is the right upper bound

Koko never needs to eat faster than the largest pile.

Why?

Because at that speed, she can finish any single pile in one hour. Going faster does not buy us anything the problem requires.

So the feasible answer must live somewhere between:

• 1
• the largest pile size

That gives the binary search a clean answer space.

Why the Feasibility Check Works

For a given speed, each pile takes:

Math.ceil(pile / speed)

hours.

The ceiling matters because Koko cannot partially spend an hour on one pile and carry the remainder into another. Each pile rounds up to a whole‑hour cost.

Add those hourly costs together across every pile, and we know whether that speed is fast enough.

Comparing the Two Approaches Honestly

The linear search version is simpler to derive:

• write the helper
• increase the speed until the helper returns true

That is not unreasonable as a first draft.

The binary‑search version is clearly better once we notice the monotonic rule:

• slower‑than‑needed speeds all fail together
• fast‑enough speeds all succeed together

That means there is a boundary between failure and success, and finding that boundary is what binary search is for.

So this is one of those problems where the key idea is not a trick inside the helper. The key idea is choosing the right thing to search over.

Why This is Different from Ordinary Binary Search

In the classic version, we binary‑search a sorted list of values.

Here we binary‑search a range of candidate answers and use a predicate to ask:

• does this candidate satisfy the constraints?

That is a pattern worth keeping because it turns up in many other problems where the answer is an integer or capacity rather than an array position.

Common Mistakes

Searching the Pile Indices Instead of the Speed Range

The array is input data. The answer lives in the space of possible eating speeds.

Using Floor Division Instead of Ceiling

That undercounts the hours needed whenever a pile does not divide evenly by the speed.

Returning Immediately on the First Working Speed Found in Binary Search

We are not looking for any working speed. We are looking for the smallest one.

Which Solution is Best?

For this problem, binary search on the answer is the best solution by a long way. The brute‑force version is only useful as a stepping stone towards the real observation.

The reason is not just performance. It is also conceptual neatness. Once we describe the helper as a monotonic feasibility test, the whole problem becomes much more disciplined.

The Part Worth Remembering

• The answer space is the range of possible speeds, not the input array.
• The helper function creates a monotonic true‑or‑false boundary.
• Binary search is the right tool for finding the smallest speed on the successful side of that boundary.

Koko Eating Bananas is a strong problem because it broadens what binary search feels like. We stop thinking of it as "search a sorted array" and start thinking of it as "find the boundary where feasibility changes".