Interview Concept: Binary Search on Answer Pattern Explained

Overview

Some problems do not search an array at all — they search a range of possible answers. If you can write a fast yes/no test feasible(x) that is monotone (once it becomes true it stays true, or vice versa), you can binary-search the smallest or largest x that works. This is often called parametric search or "binary search on the answer".

When Does It Apply?

• The answer is a single number in a known range [lo, hi].
• There is a predicate feasible(x) that flips exactly once as x increases.
• Typical phrasings: "minimise the maximum", "maximise the minimum", "smallest/largest value such that…".

Reusable Template

Python

def binary_search_on_answer(lo, hi, feasible):
    # finds the smallest x in [lo, hi] with feasible(x) == True
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Java

int binarySearchOnAnswer(int lo, int hi, IntPredicate feasible) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible.test(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;   // smallest feasible value
}

C++

int binarySearchOnAnswer(int lo, int hi, function<bool(int)> feasible) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;   // smallest feasible value
}

Classic Examples

• Koko Eating Bananas — smallest eating speed that finishes in time.
• Capacity To Ship Packages / Split Array Largest Sum — minimise the maximum load.
• Aggressive Cows / Allocate Pages — maximise the minimum / minimise the maximum.
• Smallest Divisor Given a Threshold — smallest divisor meeting a sum limit.

Key Takeaways

• Separate the two concerns: the binary search, and the feasible(x) check.
• Complexity = O(check cost × log(range)).
• To maximise instead of minimise, flip the predicate or search for the last true value.
• Reference: parametric search; LeetCode 875, 1011, 410, 1283.