Ternary Search

Find the extremum of a unimodal function — one that strictly increases then strictly decreases (or the reverse). $O (lo g)$ evaluations.

The idea

Pick two interior points $m_{1} < m_{2}$ . If $f (m_{1}) < f (m_{2})$ , the maximum cannot lie in $[l o, m_{1})$ , so discard it. Each step removes a third of the interval.

double ternaryMax(function<double(double)> f, double lo, double hi) {
    for (int it = 0; it < 200; it++) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) lo = m1; else hi = m2;
    }
    return (lo + hi) / 2;
}

Use a fixed iteration count. 200 iterations shrink the interval by $(2/3)^{200}$ , far past double precision, and the loop always terminates.

Integer ternary search

long long lo = 0, hi = n;
while (hi - lo > 2) {
    long long m1 = lo + (hi - lo) / 3;
    long long m2 = hi - (hi - lo) / 3;
    if (f(m1) < f(m2)) lo = m1 + 1; else hi = m2;
}
long long best = lo;
for (long long i = lo; i <= hi; i++) if (f(i) > f(best)) best = i;

Always finish with a small linear scan — the $\pm 1$ boundary is where integer ternary search goes wrong, and scanning 3 values costs nothing.

Strict unimodality is required

Plateaus break it
If $f (m_{1}) = f (m_{2})$ on a flat region, neither side can be safely discarded, and the search may converge to the wrong point. If the function has plateaus, use binary search on the derivative instead:
// find the last i with f(i+1) >= f(i)
while (lo < hi) { int mid = (lo+hi)/2; if (f(mid) < f(mid+1)) lo = mid+1; else hi = mid; }
This handles plateaus correctly and uses one evaluation per step instead of two.

Golden section search

Replace the thirds with the golden ratio $ϕ$ and reuse one evaluation per iteration:

const double R = (sqrt(5.0) - 1) / 2;      // 0.618...
double m1 = hi - R * (hi - lo), m2 = lo + R * (hi - lo);
double f1 = f(m1), f2 = f(m2);
for (int it = 0; it < 200; it++) {
    if (f1 < f2) { lo = m1; m1 = m2; f1 = f2; m2 = lo + R*(hi-lo); f2 = f(m2); }
    else         { hi = m2; m2 = m1; f2 = f1; m1 = hi - R*(hi-lo); f1 = f(m1); }
}

One evaluation per iteration instead of two, with a slightly slower interval shrink — a net win of about 30% when $f$ is expensive. See Golden Section Search.

Where it applies

Problem	Unimodal in
Minimise a convex function	any convex $f$
Optimal position on a line/segment	the parameter
Best speed/time trade-off	the free variable
Maximum of $f (x) =$ (something increasing) $+$ (something decreasing)	$x$
Distance from a point to a convex curve	the parameter
Nested ternary search over 2 variables	$f (x, \cdot)$ unimodal in $y$ for each $x$ , and the resulting $g (x)$ unimodal
Extreme point on a convex polygon	the vertex index (cyclically unimodal)

Nested ternary search

For a 2D convex objective:

auto g = [&](double x) { return ternaryMin([&](double y){ return f(x,y); }, ylo, yhi); };
double bestX = ternaryMin(g, xlo, xhi);

$O (lo g^{2})$ evaluations. Valid when $f$ is convex in each variable and the partial minimum $g$ is unimodal — true for jointly convex $f$ . This solves the geometric median and similar facility-location problems to arbitrary precision.

Alternatives for finding an optimum

Situation	Method
Unimodal, continuous	ternary / golden section
Unimodal, integer	ternary + final scan, or binary search on the difference
Differentiable, want a root of $f^{'}$	Newton’s method
Convex, high dimension	gradient descent, or LP
Not unimodal	simulated annealing, grid search + local refinement
Discrete with monotone feasibility	binary search on the answer
Convex sequence, DP	Aliens trick

See also: Binary Search · Golden Section Search · Newton’s Method

whoashish's cp notes

Directory