# Parametric Search

# Parametric Search

Parametric search solves an optimization problem by repeatedly asking whether a candidate parameter value is feasible. It replaces direct optimization with a sequence of decision problems.

The most common practical form is binary search on answer. The broader idea is that an unknown optimal value can be found by using a decision procedure whose result changes monotonically with the parameter.

## Problem

Given a parameter $p$ and a feasibility predicate $F(p)$, find the smallest parameter value $p^*$ such that:

$$
F(p^*) = true
$$

Assume the predicate is monotone:

$$
false, false, false, true, true, true
$$

For maximization problems, the direction is usually reversed:

$$
true, true, true, false, false, false
$$

## Key Idea

Turn an optimization problem:

$$
\text{find the best value}
$$

into a decision problem:

$$
\text{is this value feasible?}
$$

If feasibility is monotone, the optimal value is the boundary between infeasible and feasible candidates.

## Algorithm

For an integer minimization problem:

```id="param-1"
parametric_search(lo, hi, feasible):
    # Find the smallest feasible value in [lo, hi].
    while lo < hi:
        mid = lo + (hi - lo) // 2

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

    return lo
```

For an integer maximization problem:

```id="param-2"
parametric_search_max(lo, hi, feasible):
    # Find the largest feasible value in [lo, hi].
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2

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

    return lo
```

## Example

Suppose we need the minimum machine speed needed to finish all jobs within $T$ time units.

A candidate speed $s$ is feasible if the total time needed at speed $s$ is at most $T$.

If speed $s$ is feasible, then every larger speed is also feasible. Therefore the predicate has the shape:

$$
false, false, false, true, true, true
$$

Parametric search finds the first feasible speed.

## Correctness

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

For minimization, if `feasible(mid)` is true, then `mid` is a valid answer and the optimum may be `mid` or smaller, so the algorithm sets `hi = mid`.

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

The interval shrinks until one value remains. By the invariant, that value is the optimum.

## Complexity

Let $R$ be the number of candidate parameter values and let $T_F$ be the cost of one feasibility check.

| cost               |           value |
| ------------------ | --------------: |
| feasibility checks |     $O(\log R)$ |
| total time         | $O(T_F \log R)$ |
| space              |          $O(1)$ |

For continuous parameters, the number of iterations depends on the target precision $\varepsilon$:

$$
O\left(\log \frac{hi - lo}{\varepsilon}\right)
$$

## Common Applications

| problem           | parameter         | feasibility test               |
| ----------------- | ----------------- | ------------------------------ |
| minimum capacity  | capacity          | can finish within limit        |
| minimum time      | time              | can process all work           |
| maximum distance  | distance          | can place all items            |
| minimum threshold | threshold         | graph or array condition holds |
| scheduling        | deadline or speed | schedule exists                |

## Comparison with Binary Search on Answer

Binary search on answer is the common programming implementation of parametric search.

Parametric search is the broader technique. In computational geometry and parallel algorithms, it can simulate a decision algorithm symbolically to locate the optimal parameter more directly.

## When to Use

Use parametric search when:

* the answer space is ordered
* there is an efficient feasibility test
* feasibility changes monotonically
* direct optimization is harder than checking a candidate

## Notes

* The most important step is proving monotonicity.
* Bounds must be chosen so that the answer lies inside the search interval.
* For real-valued parameters, return an approximation rather than an exact value.
* Avoid this method when the feasibility predicate is nonmonotone.

## Implementation

```id="py-parametric-search"
def parametric_search(lo, hi, feasible):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

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

```id="go-parametric-search"
func ParametricSearch(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
}

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