Searching & Selection7 min read

Binary Search on Answer

When you can't search the array — search the answer itself
time:\(O(\log(range)\) · f(n))pattern:Is X feasible? Binary search on X

Imagine you're a delivery driver who must finish a route before 6 PM. You can drive at different speeds. Drive too slow — you miss the deadline. Drive fast enough — you make it. Somewhere between 'too slow' and 'fast enough' there's a minimum speed that just barely works.

How do you find it? You could test every possible speed from 1 km/h upward — but that's painfully slow. A smarter move: test the middle speed. If that works, try slower. If it doesn't, try faster. You're doing binary search — not on an array, but on the space of possible answers.

The big idea

Regular binary search finds a value in a sorted array. Binary search on answer finds a value across the space of possible solutions to your problem. The trick only works when your answer space has a clean boundary: below some threshold the answer is "no, not feasible", and above it the answer is "yes, feasible" — always. This property is called monotonicity.

If you can write a function feasible(x) that answers "can we do it with x?", and if that function flips from false to true at exactly one point, then you can binary search for that flip point.

The template

Set lo to the minimum possible answer, hi to the maximum. Loop while lo < hi: compute mid = lo + (hi - lo) / 2. If feasible(mid) is true, the answer could be mid or something even smaller — set hi = mid. Otherwise, mid is too small — set lo = mid + 1. When the loop ends, lo == hi is your minimum feasible answer.

Classic examples

Split array into k groups (minimize max sum): Given an array and k groups, minimize the maximum group sum. For a candidate max sum x, greedily check if you can form k groups each summing to ≤ x. Binary search on x in range [max element, total sum]. Total: \(O(n · \log(total sum)\)).

Koko eating bananas: Piles of bananas, must finish in H hours. Find the minimum eating rate k. feasible(k) = can she finish all piles at rate k in H hours? Binary search on k in [1, max pile]. Total: \(O(n · \log(max pile)\)).

Integer square root: Find ⌊√n⌋ without floating point. feasible(x) = \(x^2\) ≤ n. Binary search on x in [0, n]. Total: \(O(\log n)\).

Note: The key question to ask yourself: 'If X works, does X+1 also work?' (or vice versa). If yes — the answer space is monotone, and you can binary search it. If the answer can flip back and forth, binary search on answer won't apply.

Binary Search on Answer — Koko Eating Bananas

import math


def min_eating_speed(piles, h):
    def feasible(speed):
        # Can Koko eat all piles in h hours at this speed?
        return sum(math.ceil(p / speed) for p in piles) <= h


    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid        # mid works; try slower
        else:
            lo = mid + 1    # mid too slow; go faster
    return lo


piles = [3, 6, 7, 11]
h = 8
print(min_eating_speed(piles, h))  # 4
Output
4

Complexity

🔍 Binary search phaserange = hi - lo across the answer space; often log(max_value) ≈ 30 steps
Logarithmic in answer range\(O(\log(range)\))
✅ Feasibility check (each call)Usually a linear greedy scan — \(O(n)\) per call
Depends on the problem\(O(f(n)\))
⚡ Total complexityE.g., \(O(n · \log(sum)\)) for split-array problems
Log-linear typically\(O(\log(range)\) · f(n))

Quick check

What property must the feasibility function have for binary search on answer to work?

Continue reading

Binary Search
Cut the problem in half — every single time
→
Greedy Pattern
Always grab the biggest slice of pizza — sometimes that's optimal, sometimes it isn't
→