Binary search on the answer: the pattern behind minimum speed and smallest capacity

Short answer. Binary search on the answer searches the range of possible answers. The input array stays unsorted. You guess a value and check it in O(n). Then you halve the range. It fits problems that say "minimum speed", "smallest capacity" or "maximum minimum distance". Below: the shape, the check function, Python code and Koko Eating Bananas.

What is binary search on the answer?

Classic binary search looks for a value in a sorted array. Here nothing is sorted. Instead the answers themselves form a range from low to high.

Every candidate answer allows a yes or no question: is this enough? The answers to that question are monotonic. Below some threshold all answers are "no", above it all are "yes". Binary search finds the threshold.

The method needs three things. A lower bound, an upper bound and a check function.

When does a problem need binary search on the answer?

• "Minimum speed to finish in h hours."
• "Smallest ship capacity to ship all packages in d days."
• "Split the array into k parts to minimise the largest sum."
• "Place k cows in stalls to maximise the minimum distance."

The signal is the word "minimum" or "maximum" next to a condition. Checking a fixed value is easy. Finding the best value directly is hard. That gap is what the pattern fills.

How does the check function work?

The check takes a candidate. It returns True if the candidate satisfies the task. It must be monotonic. Once True, it stays True for every larger candidate. Or the reverse, for maximising problems.

Take Koko Eating Bananas. Candidate speed k. Hours needed is the sum of ceil(pile / k) over all piles. Return True when that sum is at most h. Faster speed, fewer hours. Monotonic.

Problem	Range	Check(x)	Want
Koko Eating Bananas	1 .. max(piles)	hours at speed x <= h	smallest True
Capacity to Ship Packages	max(w) .. sum(w)	days at capacity x <= d	smallest True
Split Array Largest Sum	max(a) .. sum(a)	parts with limit x <= k	smallest True
Aggressive Cows	1 .. max gap	can place k cows at distance x	largest True

How do you write binary search on the answer in Python?

import math

def min_eating_speed(piles, h):
    lo, hi = 1, max(piles)

    def ok(k):
        return sum(math.ceil(p / k) for p in piles) <= h

    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid          # mid works, try smaller
        else:
            lo = mid + 1      # mid fails, need bigger
    return lo

# maximising version: largest x with ok(x) True
def largest_ok(lo, hi, ok):
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if ok(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

The loop keeps lo as the smallest value that could still work. When lo meets hi, that is the answer. The +1 in the maximising version stops an infinite loop.

What does one run look like?

Piles [3, 6, 7, 11], h = 8. Range 1 to 11. Try 6: hours are 1 + 1 + 2 + 2 = 6. Fine, so hi = 6. Try 3: hours are 1 + 2 + 3 + 4 = 10. Too many, so lo = 4.

Try 5: hours are 1 + 2 + 2 + 3 = 8, fine, hi = 5. Try 4: hours are 1 + 2 + 2 + 3 = 8, fine, hi = 4. Now lo equals hi. Answer 4.

Four checks instead of eleven. With a range up to a billion, it is thirty checks.

How do you pick the bounds?

The lower bound is the smallest value that makes sense. For a speed that is 1. For a capacity it is the largest single item, or nothing ships.

The upper bound is a value that surely works. The largest pile, the sum of all weights. A loose upper bound costs a few extra checks. Err on the large side.

What mistakes break binary search on the answer?

• A check that is not monotonic. Then the halving throws away the answer.
• Bounds that exclude the answer. Capacity below the largest item never ships it.
• Using mid = (lo + hi) // 2 while maximising. lo = mid then never moves.
• Integer division in the check where ceiling was needed.

How do you explain binary search on the answer in an interview?

Say: "I cannot compute the answer directly, but I can verify a guess in O(n)." Then say the verification is monotonic. Then name the bounds. Then write the loop.

State the complexity as O(n log(hi - lo)). The log is over the answer range, not the array. Interviewers check that you know which log it is.

Practise spotting this pattern on the binary search on the answer page. The array version lives on the binary search page.

FAQ

How is this different from ordinary binary search?

Ordinary binary search compares mid with a target inside a sorted array. This one calls a check function on mid. The array does not need to be sorted at all.

Can the answer be a floating point number?

Yes. Loop a fixed number of times, around 100. Do not wait for lo to equal hi. Or stop when hi - lo is below the required precision.

What if the check is O(n log n)?

Then the total is O(n log n log R). Usually that still passes. Sorting once outside the loop often brings the check back to O(n).