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:

Assume the predicate is monotone:

For maximization problems, the direction is usually reversed:

Key Idea

Turn an optimization problem:

into a decision problem:

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

Algorithm

For an integer minimization problem:

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:

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:

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.

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

Common Applications

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

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

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
}