IntermediateBinary Search

Binary search on the answer

When “is speed k enough?” flips from no to yes as k grows, binary search over k itself, even though nothing is sorted.

The idea

Some problems ask for the smallest value that works. If you can check a candidate quickly, and every value above a working one also works, the answers form “no no no yes yes yes”. Binary search finds the first yes.

You search over a range of possible answers, not over the array.

Worked example

Koko Eating Bananas: piles [3, 6, 7, 11], h = 8 hours

Speeds 1…11 are possible. Hours needed at speed k = sum of ceil(pile / k).
k=6 → 1+1+2+2 = 6 ≤ 8 ✓ → try smaller
k=3 → 1+2+3+4 = 10 > 8 ✗ → go bigger
k=4 → 1+2+2+3 = 8 ✓ → smallest speed is 4

In code (Python)

def min_eating_speed(piles, h):
    def hours(k):
        return sum((p + k - 1) // k for p in piles)  # ceil(p / k)

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if hours(mid) <= h:
            hi = mid          # mid works; maybe something smaller does too
        else:
            lo = mid + 1      # too slow
    return lo

O(n log m), m = the largest pile.

How to spot it

“minimum speed / capacity / days such that…”, with a quick yes/no check for a given value.

Common mistakes

`hi = mid - 1` after a success, which can skip the answer.
Floating-point division where you need a ceiling.

Practise it

Go further

Up next for you · Beginner

“Have I seen this?” is a set →

All tips