Binary Search on Answer in Python: Koko Eating Bananas

Find the minimum eating speed so Koko finishes all banana piles within a given hour limit using binary search on the answer.

Medium Python 3.9+ Aug 9, 2026 Algorithms & data structures 15 views 0 copies

binary-search algorithms search math

Python code

21 lines

Python 3.9+

import math

def min_eating_speed(piles, h):
    """Return minimum integer eating speed K so Koko finishes within h hours."""
    def hours_needed(speed):
        return sum(math.ceil(p / speed) for p in piles)

    low, high = 1, max(piles)
    while low < high:
        mid = (low + high) // 2
        if hours_needed(mid) <= h:
            high = mid
        else:
            low = mid + 1
    return low

if __name__ == "__main__":
    piles = [3, 6, 7, 11]
    h = 8
    result = min_eating_speed(piles, h)
    print(f"Minimum eating speed: {result} bananas/hour")

Output

stdout

Minimum eating speed: 4 bananas/hour

How it works

This solution uses binary search over the possible eating speeds (from 1 to the largest pile) because the required time monotonically decreases as speed increases. The hours_needed helper computes total hours by summing the ceiling of each pile divided by the speed, using math.ceil. The binary search narrows the range to the smallest speed that still finishes within h hours by moving high down when the speed is sufficient and low up when it isn't. This transforms a linear search into O(n log max(piles)) time, where n is the number of piles.

Common mistakes

Forgetting to use math.ceil, which undercounts hours when a pile isn't evenly divisible by the speed.
Setting the binary search low bound to 0, which causes a division-by-zero error.
Using if/else with `return mid` in the loop instead of narrowing `low`/`high` and continuing until they meet.
Confusing the monotonicity direction — hours decrease as speed increases, so the condition must check `<= h`.

Variations

Use a linear scan from 1 to max(piles) for very small inputs, checking each speed until one fits.
Implement with a while loop over speeds and `sum((p + speed - 1) // speed for p in piles)` to avoid importing math.

Real-world use cases

Optimizing batch job scheduler time by finding the minimal worker throughput to meet a deadline.
Determining the minimal rate for a rate-limited API consumer to drain a message queue within a window.
Calculating the minimum download speed needed to complete large transfers before a scheduled cutover.

Binary Search on Answer in Python: Koko Eating Bananas

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes