# Binary Search on Answer

# 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

```id="bsoa-1"
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

```id="py-bsoa"
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
```

```id="go-bsoa"
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
}
```