Binary Search & Monotonic Spaces

Binary Search on Answer Space is one of the highest-leverage algorithmic patterns you can learn. Once you recognize it, dozens of seemingly hard problems (shipping packages, splitting arrays, cutting ribbons, allocating memory) all collapse into the exact same 15 lines of code.

1. When Can You Use This Pattern?

Ask yourself one simple question: Is the condition monotonic?

• If Koko eats at speed k = 100 bananas/hour and succeeds in finishing in under h hours, would eating at speed k = 101 also succeed? Yes, always.
• If eating at speed k = 5 is too slow and fails, would eating at speed k = 4 also fail? Yes, always.

Because the outcome transitions cleanly from False, False, ..., True, True, True, the answer space is monotonic. That means we don’t need to test every speed from 1 to 1 billion linearly—we can binary search it in O(log(MaxPile)) steps!

2. The Integer Ceiling Trick (Say Goodbye to Float Bugs)

If Koko has a pile of 7 bananas and eats at speed k = 3, she needs ceil(7 / 3) = 3 hours.

In Python or C++, doing math.ceil(pile / k) converts the numbers to IEEE-754 64-bit floats. On massive numbers (e.g. 10^14), floating-point precision degrades, causing silent off-by-one errors.

The standard integer arithmetic replacement for ceil(a / b) is:

hours = (pile + k - 1) // k

Let’s test it: (7 + 3 - 1) // 3 = 9 // 3 = 3. Exactly right, 100% integer math, zero float conversions!

3. Clean Python 3.12 Implementation

from typing import Sequence

def min_eating_speed(piles: Sequence[int], h: int) -> int:
    """Finds minimum integer eating speed k such that total hours <= h."""
    
    # Lower bound: Koko must eat at least 1 banana per hour
    # Upper bound: Eating faster than the largest pile doesn't save any more time
    low = 1
    high = max(piles)
    ans = high

    def can_finish(speed: int) -> bool:
        total_hours = 0
        for pile in piles:
            # Equivalent to ceil(pile / speed) without floats
            total_hours += (pile + speed - 1) // speed
            if total_hours > h:
                return False  # Early exit optimization
        return total_hours <= h

    while low <= high:
        mid = low + (high - low) // 2
        
        if can_finish(mid):
            ans = mid         # mid is valid, but can we go even slower?
            high = mid - 1    # try searching left
        else:
            low = mid + 1     # too slow, must eat faster

    return ans

4. Complexity & Production Benchmarks

• Time Complexity: O(N * log(M)) where N is the number of piles and M is max(piles). If M = 10^9, log2(10^9) ≈ 30. Even with 100,000 piles, the validation function runs at most 30 times. Total operations: ~3 million, executing in under 15 milliseconds.
• Space Complexity: O(1) auxiliary memory.
• Overflow Note for C++ / Java: In C++, total_hours can easily exceed 2^31 - 1 if speeds are small and piles are large. Always declare int64_t total_hours = 0; to prevent integer overflow.