Binary Search on Answer

Binary search on answer finds an optimal numeric value by searching over possible answers instead of searching over array indices. It is used when a direct formula is difficult, but a candidate answer can be tested efficiently.

The method requires a monotone feasibility condition. For minimization problems, the predicate often has the form:

false, false, false, true, true, true

For maximization problems, it often has the form:

true, true, true, false, false, false

Problem

Given a range of possible answers and a predicate $P(x)$ , find the smallest feasible value $x$ such that

P(x) = true

The predicate must be monotone: once a value becomes feasible, all larger values must also be feasible.

Key Idea

Convert an optimization problem into a decision problem.

Instead of asking:

\text{What is the best answer?}

ask:

\text{Is this candidate answer feasible?}

Then use binary search to find the boundary between infeasible and feasible values.

Algorithm

binary_search_on_answer(lo, hi, feasible):
    # Search in the inclusive range [lo, hi].
    # Assumes at least one feasible value exists.
    while lo < hi:
        mid = lo + (hi - lo) // 2

        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1

    return lo

Example

Suppose we need the smallest capacity needed to ship packages within $d$ days.

A candidate capacity $c$ is feasible if the packages can be shipped in at most $d$ days using ships of capacity $c$ .

If capacity $c$ is feasible, then every larger capacity is also feasible. Therefore the predicate is monotone.

capacity	feasible
too small	false
still too small	false
minimum valid capacity	true
larger capacity	true

Binary search finds the first true capacity.

Correctness

The algorithm maintains the invariant that the optimal answer lies in the current interval $[lo, hi]$ .

If feasible(mid) is true, then mid is a valid answer, but a smaller valid answer may still exist, so the algorithm keeps the left half by setting hi = mid.

If feasible(mid) is false, then monotonicity implies that every value less than or equal to mid is also infeasible, so the algorithm removes them by setting lo = mid + 1.

When lo = hi, only one candidate remains. By the invariant, it is the smallest feasible answer.

Complexity

Let $R$ be the number of candidate values in the search range, and let $T_P$ be the cost of checking feasibility.

cost	value
feasibility checks	$O(\log R)$
total time	$O(T_P \log R)$
extra space	$O(1)$

For integer ranges, $R = hi - lo + 1$ .

Choosing Bounds

Good bounds make the search safer and faster.

bound	meaning
`lo`	smallest possible answer
`hi`	largest answer that is certainly feasible

For the shipping capacity example:

lo = max(package_weight)
hi = sum(package_weight)

The lower bound must rule out impossible answers. The upper bound must guarantee feasibility.

Common Patterns

problem type	predicate shape	result
minimize maximum load	false then true	first feasible
minimize time	false then true	first feasible
maximize minimum distance	true then false	last feasible
maximize score under constraint	true then false	last feasible

Implementation

def binary_search_on_answer(lo, hi, feasible):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

func BinarySearchOnAnswer(lo, hi int, feasible func(int) bool) int {
    for lo < hi {
        mid := lo + (hi-lo)/2
        if feasible(mid) {
            hi = mid
        } else {
            lo = mid + 1
        }
    }
    return lo
}