Golden Section Search

Ternary search refined so that one function evaluation is reused each iteration. Same $O(\log )$ convergence, roughly 30% fewer evaluations.

The idea

Ternary search evaluates $f$ at two new interior points every iteration and discards both. Golden section chooses the points so that after discarding one side, one of them is still interior and correctly placed for the next round.

The ratio that makes this work is the golden ratio: $\rho =\frac{\sqrt{5}-1}{2}\approx 0.618$.

const double R = 0.6180339887498949;         // (sqrt(5) - 1) / 2
 
double goldenMin(function<double(double)> f, double lo, double hi) {
    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) {
            hi = m2; m2 = m1; f2 = f1;
            m1 = hi - R * (hi - lo); f1 = f(m1);      // ONE new evaluation
        } else {
            lo = m1; m1 = m2; f1 = f2;
            m2 = lo + R * (hi - lo); f2 = f(m2);      // ONE new evaluation
        }
    }
    return (lo + hi) / 2;
}

Evaluations compared

Method	Interval shrink per iteration	Evaluations per iteration	Shrink per evaluation
Ternary	$\times 2/3$	2	$\sqrt{2/3}\approx 0.816$
Golden section	$\times 0.618$	1	$0.618$

Lower is better, so golden section wins: to shrink by a factor $10^{-9}$ it needs about 43 evaluations versus ternary’s 51. The saving matters when $f$ is expensive — a simulation, a nested search, or a flow computation.

Fibonacci search

The discrete analogue: use consecutive Fibonacci numbers as the interval splits. Optimal for minimising the worst-case number of evaluations over a fixed number of integer candidates, and it needs no floating-point ratio.

F(k) candidates  ->  k evaluations

Mostly of theoretical interest; golden section is simpler and effectively as good.

Requirements and failure

The function must be strictly unimodal on the interval. As with ternary search:

Plateaus break it

If $f(m_1)=f(m_2)$ on a flat region, neither side can be discarded safely. For functions with flat regions, binary search on the difference $f(i+1)-f(i)$ instead.

When to use which

Situation	Method
$f$ cheap, want simplicity	ternary search
$f$ expensive (simulation, nested search, flow)	golden section
$f$ differentiable and well-behaved	Newton on $f’$
Integer domain	ternary + a final linear scan
Not unimodal	grid search + local refinement, or annealing
Convex, discrete, DP-shaped	Aliens trick

Where it appears

• Nested searches — a 2D optimisation where the inner call is itself a search; halving the outer evaluations halves the total work.
• Physical optimisation — best launch angle, optimal speed, minimum-time trajectories.
• Parameter tuning inside a heuristic solver.
• Geometry — the closest point on a convex curve, the optimal position along a segment.

The golden ratio’s role

$\rho$ satisfies ${\rho }^2=1-\rho$, which is exactly the condition that the reused point sits at the correct proportional position in the new, smaller interval. That self-similarity is the whole reason the ratio appears — the same property that makes $\varphi$ show up in Fibonacci growth and in continued fractions.

See also: Ternary Search · Newton’s Method · Fibonacci Numbers