Coding Patterns

Binary Search on Answer

A powerful interview pattern where you binary search the range of possible answers instead of searching inside a sorted array.

Binary SearchCoding PatternOptimizationMonotonic Predicate

The Short Answer

Binary search on answer is used when you are not searching for an element in a sorted array. Instead, you are searching for the smallest or largest answer that satisfies a condition.

The trick is to turn the problem into a yes/no question: “Does this candidate answer work?”

If the answer is monotonic — for example, all smaller values fail and all larger values pass — then binary search can find the boundary.

The Mental Model

Classic binary search looks inside a sorted array. Binary search on answer searches a range of possible answers.

Classic Binary Search

Search for a target inside sorted data.

Binary Search on Answer

Search for the first passing answer.

A Concrete Example: Eating Bananas

Suppose Koko has piles of bananas and must finish within a fixed number of hours. The question is:

What is the minimum eating speed that lets her finish on time?

This does not look like binary search at first because there is no sorted array to search.

But the possible speeds are ordered:

Slow speeds fail. Fast enough speeds pass. We want the first speed that passes.

So we binary search on the range of speeds, to find the smallest speed that satisfies a criterion. In this case, that is the leftmost - i.e. the first valid answer - of the green values towards the right. We don't need to make the calculation for every speed, as that would make it O(n). We don't need to try every possible speed one by one, because for each speed we would still need to scan all piles. Instead we binary search on the range of speeds, reducing the time complexity to O(log(n)). In fact, for this Koko Eating Bananas problem, it is O(n log m), where n is the number of piles and m is the maximum pile size. There are separate pages covering this category of problems.

The Key Question

For every candidate answer, ask:

java

boolean canFinish(int speed) {
    // return true if this speed is enough
}

If speed 4 works, then speed 5, 6, 7, and higher also work. That is the monotonic property.

Binary search on answer works when the search space has a clean failure-to-success or success-to-failure boundary.

General Java Template

java

public int binarySearchOnAnswer(int low, int high) {
    while (low < high) {
        int mid = low + (high - low) / 2;

        if (can(mid)) {
            high = mid;      // mid works, try smaller answer
        } else {
            low = mid + 1;   // mid does not work, need bigger answer
        }
    }

    return low;
}

This version finds the minimum value that works. That is the most common version in interview problems.

How to Recognize This Pattern

Look for wording like:

Minimum possible maximum
Smallest speed
Minimum capacity
Largest minimum distance
Can we do this within K days?
Can we split this into at most K parts?

If the problem asks for an optimal number and you can test whether a candidate number is feasible, think binary search on answer.

Common Problems That Use This Pattern

Koko Eating Bananas (TBD)

Search for the minimum eating speed that finishes all piles within H hours.

Capacity to Ship Packages (TBD)

Search for the minimum ship capacity that can deliver all packages within D days.

Split Array Largest Sum (TBD)

Search for the smallest possible largest subarray sum.

Aggressive Cows (TBD)

Search for the largest minimum distance between placed cows.

Minimum That Works vs Maximum That Works

There are two common versions.

Find Minimum That Works

Return the first true.

Find Maximum That Works

Return the last true.

Why Interviewers Like This Pattern

This pattern tests more than syntax. It tests whether you can recognize a hidden structure.

Many candidates only associate binary search with sorted arrays. But in harder interview problems, the sorted thing is often invisible. It is the sequence of yes/no answers.

The “array” you are searching is not given directly. You create it by asking whether each candidate answer works.

Common Mistakes

Using binary search when the predicate is not monotonic

If true and false values are mixed randomly, binary search does not apply.

Choosing bad low and high bounds

The lower and upper bounds should cover every possible valid answer.

Forgetting what can(mid) means

Before coding, clearly define whether can(mid) means mid is enough, too small, too large, or feasible.

Returning the wrong boundary

Know whether the problem asks for the first true, last true, minimum feasible answer, or maximum feasible answer.

Final Takeaway

Binary search on answer is not about finding a value in a sorted array. It is about finding the boundary where impossible becomes possible.