Binary Search Beyond Sorted Arrays: The Search-on-Answer Pattern

Most people learn binary search as "find a target in a sorted array" and stop. Then they meet Koko Eating Bananas, or Split Array Largest Sum, and cannot see why the editorial says binary search when there is nothing sorted in sight.

The thing being searched is not the array. It is the answer.

The shape of a search-on-answer problem

You are asked for the smallest (or largest) value of something: the slowest eating speed that finishes in time, the smallest ship capacity that delivers in D days, the minimum largest-sum when you split an array into k parts.

Two properties make it binary-searchable:

1. Checking a candidate is easy. Given a speed, you can simulate and see whether Koko finishes in time in O(n).
2. The check is monotonic. If speed 5 works, speed 6 works. If capacity 10 fails, capacity 9 fails. Plot "does it work" against the candidate value and you get a run of false followed by a run of true. The boundary is the answer.

Once you see that boundary, the problem collapses to: binary search over the candidate range, with the check as the comparison.

The template

Write it the same way every time. This one finds the first value in [lo, hi] for which ok(x) is true.

def first_true(lo, hi, ok):
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid        # mid works, answer is mid or to the left
        else:
            lo = mid + 1    # mid fails, answer is strictly to the right
    return lo

Three details that stop it looping forever or landing one off:

• while lo < hi, not <=. The loop ends when the range is a single value, which is the answer.
• The success branch keeps mid in the range (hi = mid); the failure branch excludes it (lo = mid + 1). Because mid rounds down, lo always moves forward.
• Pick lo and hi so the answer is guaranteed inside. For Koko, lo = 1 and hi = max(piles).

For "last true" problems, mirror it: mid = (lo + hi + 1) // 2, lo = mid on success, hi = mid - 1 on failure.

Worked example: Koko Eating Bananas

Koko has piles of bananas and h hours. At speed k she eats one pile per hour, up to k bananas from it. Find the minimum k.

• Candidate range: 1 to the largest pile.
• Check: sum(ceil(p / k) for p in piles) <= h. O(n).
• Monotonic: faster always finishes sooner. Yes.

import math

def min_eating_speed(piles, h):
    def ok(k):
        return sum(math.ceil(p / k) for p in piles) <= h
    return first_true(1, max(piles), ok)

Total O(n log M) where M is the largest pile. The binary search visualizer shows the lo/hi/mid dance on a plain array; the search-on-answer version moves the same three pointers over the candidate range instead.

The problems that use it

All of these are "hard-looking, easy once you see it":

• Koko Eating Bananas (minimum speed)
• Capacity to Ship Packages Within D Days (minimum capacity)
• Split Array Largest Sum (minimum of the maximum part)
• Minimum Number of Days to Make m Bouquets (minimum days)
• Magnetic Force Between Two Balls (maximum minimum distance, a "last true")
• Minimum Time to Complete Trips
• Aggressive Cows, the classic version from competitive programming

Notice the wording: minimum speed, minimum capacity, minimum days, maximum distance. A superlative over a numeric quantity plus a feasibility check is the fingerprint.

The two mistakes interviewers see most

Searching the wrong range. Setting hi to the array length when the answer is a sum, or to the sum when the answer is a count. Write down what the candidate is (a speed, a capacity, a day count) and set the range in those units.

A check that is not monotonic. Occasionally the feasibility function is not a clean false-then-true run, and binary search silently returns garbage. Before coding, say out loud why a larger candidate can never turn a success into a failure. If you cannot, it is not this pattern.

Where it sits in a plan

Binary search is a 16-problem topic in the curated set, and roughly half of those are search-on-answer. It is core for every SDE role, and it is the one topic where five well-chosen problems transfer almost completely to the rest, because the template does not change. Learn the plain sorted-array version first, then the rotated-array variants, then this. After that, every new binary search problem is a ten-minute problem.