Koko Eating Bananas

No sorted array in sight. Instead: "find the minimum speed / smallest capacity / least X such that a condition is satisfiable." When the answer itself lives in a numeric range and feasibility is monotonic, you binary search the ANSWER, not the input. This is THE pattern interviewers love because it looks nothing like binary search at first.

Try every eating speed starting at 1. For each one, add up the hours Koko needs, and return the first speed that fits inside the allowed hours.

O(max(piles) * n) time, since each candidate speed costs a full pass over the piles.

The piles can hold a billion bananas, so the loop over candidate speeds is the expensive part, not the check. That should make you look at the sequence of answers rather than the piles. Speed 1 is too slow, and so is 2, and so is 3, until at some point a speed works and then every larger speed also works. The answers form a run of no followed by a run of yes, and that shape is exactly what binary search consumes.

The array you binary search is not the input. It is the range of possible answers, from a speed of 1 up to the largest pile, because eating faster than the largest pile cannot help.

For this to be legal the question you ask has to be monotonic. Here the question is whether Koko finishes within the allowed hours at speed k. If she finishes at speed k then she certainly finishes at any speed above k, so once the answer becomes yes it never goes back to no. That single property is what lets you discard half the speeds at a time, and it is the thing to check before reaching for this pattern.

You want the smallest speed that works, which is the boundary between the no block and the yes block. When the middle speed works you keep it as a candidate and search the lower half, because something smaller might also work. When it fails you know the middle and everything below it are out, so you move past it. The loop ends when the range collapses onto a single value, and that value is the answer.

import math

def minEatingSpeed(piles, h):
    def feasible(k):                       # monotonic in k
        return sum(math.ceil(p / k) for p in piles) <= h

    lo, hi = 1, max(piles)
    while lo < hi:                         # leftmost-true (Template B)
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid                       # maybe smaller works
        else:
            lo = mid + 1                   # need to eat faster
    return lo

The hours for one pile are the pile size divided by the speed, rounded up. Integer division rounds down, so write it as (pile + k - 1) / k or use an explicit ceiling. Rounding down here is the most common bug in this problem and it silently reports that Koko is faster than she is.

The condition is lo < hi, not lo <= hi, and the successful branch sets hi = mid rather than mid - 1. That pairing is deliberate. mid might be the answer, so it has to stay inside the range, and lo < hi is what stops that from looping forever.

When the loop ends lo and hi are equal, so returning either one is correct. There is no separate not-found case, because the largest pile is always a working speed.