ii. Ternary and Golden-Section Search

These find the extremum of a unimodal function (strictly increasing then strictly decreasing, or the reverse) with $O(\log )$ evaluations. Convex and concave functions are the main source of unimodality.

Real ternary search

template<class F> double ternaryMin(F f, double lo, double hi) {
    for (int it = 0; it < 100; it++) {              // (2/3)^100 ~ 1e-18 of the range
        double m1 = lo + (hi - lo) / 3, m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) hi = m2; else lo = m1;
    }
    return (lo + hi) / 2;
}

Use a fixed iteration count, as in binary search.

Proof: discarding a third is safe for a unimodal (here, convex-shaped: decreasing then increasing) $f$

Let $x^{\ast }$ be the minimiser. If $f(m_1)<f(m_2)$ with $lo<m_1<m_2<hi$: claim $x^{\ast }\notin (m_2,hi]$. If it were, $f$ would be strictly decreasing on $[m_1,m_2,x^{\ast }]$ in particular at $m_1,m_2$ (both before the minimum, on the decreasing branch — wait, more carefully): since $f$ is decreasing then increasing with minimum at $x^{\ast }$, if $x^{\ast }>m_2$ then both $m_1,m_2$ are on the decreasing branch, so $f(m_1)>f(m_2)$ (further left is higher) — contradicting $f(m_1)<f(m_2)$. So $x^{\ast }\le m_2$, justifying hi=m2. Symmetrically, if $f(m_1)\ge f(m_2)$, $x^{\ast }\ge m_1$, justifying lo=m1. Either way the discarded third provably cannot contain $x^{\ast }$, and the kept interval still contains it; after $t$ iterations the interval has shrunk by a factor $(2/3{)}^t$ (each step evaluates two new points dividing the interval into three parts and keeps two of them), reaching $\approx 10^{-18}$ of the original range at $t=100$. $■$

Integer domain: binary search the slope

On integers, binary search the first $i$ with $f(i+1)-f(i)\ge 0$. That uses one comparison per step and handles plateaus at the optimum. Ternary search on integers needs a final linear scan of the last 3 candidates anyway.

ll lo = L, hi = R;                       // find argmin of convex f on [L, R]
while (lo < hi) {
    ll mid = lo + (hi - lo) / 2;
    if (f(mid) <= f(mid + 1)) hi = mid; else lo = mid + 1;
}

Proof: binary search on the slope finds the argmin

For convex $f$ on integers, the difference $d(i)=f(i+1)-f(i)$ is non-decreasing (discrete convexity, by definition). So $d(i)\ge 0$ is a monotone predicate ($F\dots FT\dots T$ in $i$): once the slope turns non-negative it stays non-negative. The code’s predicate f(mid)<=f(mid+1) is exactly $d(mid)\ge 0$, and binary-searching its first true position finds the smallest $i$ with $d(i)\ge 0$, i.e. the smallest $i$ where $f$ stops decreasing — which, for convex $f$, is exactly where the (possibly flat) minimum begins. $■$

Plateaus

Unimodality must be strict away from the optimum. If $f(m_1)=f(m_2)$ on a flat region that isn’t the optimum, neither side can be discarded and ternary search can converge to the wrong place. Convex functions are fine, since a flat part of a convex function is the minimum.

Golden-section search

This reuses one evaluation per iteration. The points sit at ratio $\rho =(\sqrt{5}-1)/2\approx 0.618$, and because ${\rho }^2=1-\rho$ the surviving point is exactly where the next iteration needs it.

template<class F> double goldenMin(F f, double lo, double hi) {
    const double R = (sqrt(5.0) - 1) / 2;
    double m1 = hi - R * (hi - lo), m2 = lo + R * (hi - lo), f1 = f(m1), f2 = f(m2);
    for (int it = 0; it < 100; it++) {
        if (f1 < f2) { hi = m2; m2 = m1; f2 = f1; m1 = hi - R * (hi - lo); f1 = f(m1); }
        else         { lo = m1; m1 = m2; f1 = f2; m2 = lo + R * (hi - lo); f2 = f(m2); }
    }
    return (lo + hi) / 2;
}

Method	Shrink per evaluation	Evaluations for $10^{-9}$ relative
ternary	$\sqrt{2/3}\approx 0.816$	about 103
golden section	$0.618$	about 43

Proof: golden-section search reuses the correct point

With $L=hi-lo$, the construction places $m_1=lo+(1-\rho )L$ and $m_2=lo+\rho L$. Say $f(m_1)<f(m_2)$, so the code discards $(m_2,hi]$: the new interval is $[lo,m_2]$ of length $L^{\prime }=\rho L$, and the old $m_1$ is reused as the new $m_2$ (the code does m2 = m1) rather than recomputed. For this reuse to be correct, old $m_1$‘s offset from $lo$, which is $(1-\rho )L$, must equal what the construction rule would have placed at the new $m_2$ for the new interval, namely $\rho \cdot L^{\prime }=\rho \cdot (\rho L)={\rho }^{2}L$. Requiring $(1-\rho )L={\rho }^{2}L$ gives exactly ${\rho }^2=1-\rho$, i.e. ${\rho }^2+\rho -1=0$, with positive root $\rho =\frac{\sqrt{5}-1}{2}$ — so this specific $\rho$ is exactly the value making the reuse land correctly (the symmetric case, discarding the left side and reusing old $m_2$ as new $m_1$, gives the same equation). $■$

Golden section matters when $f$ is expensive: a nested search, a flow or DP per evaluation, or a simulation. The discrete analogue is Fibonacci search: with $F_k$ integer candidates it needs $k$ evaluations, which is optimal in the worst case.

Where unimodality comes from

Source	Example
convex function (sum of convex terms)	$\sum |x-a_i|$, $\sum (x-a_i{)}^2$, ${\max }_i|x-a_i|$, distance from a moving point
increasing + decreasing trade-off	”spend $x$ on upgrades, then the rest of the time working”
minimum over a family of convex functions in a parameter	the lower envelope is not convex, so be careful
cost of $k$ groups in partition DPs	convex in $k$ (Aliens trick)
extreme point of a convex polygon in a direction	unimodal along the boundary (cyclically): binary search on edges
distance between two points moving linearly	$|p+vt|$ is convex in $t$

The sum of convex functions is convex, the max of convex functions is convex, and convex composed with affine is convex. The sum of two unimodal functions is not unimodal in general. Prove convexity rather than assuming unimodality.

Nested ternary search

For a jointly convex $f(x,y)$, $g(x)={\min }_{y}f(x,y)$ is convex, so

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

and a ternary search over $x$ finishes the job in $O({\log }^2)$ evaluations. Typical uses: the geometric median (Weber point), the smallest enclosing circle of moving points, best meeting point under Euclidean distance, best launch angle / minimum-time trajectory problems, and parameter tuning inside a heuristic solver. Each extra dimension multiplies the cost by $\log$, so beyond 2-3 dimensions use gradient methods or random restarts plus hill climbing (Heuristics).

Alternatives

Situation	Method
derivative available	Newton’s method or bisection on $f^{\prime }$
discrete and convex	binary search on $f(i+1)-f(i)$; or slope trick if it’s DP-shaped
not unimodal, low dimension	grid sample, then refine around the best few points
convex in many variables, linear constraints	LP / simplex
piecewise linear convex	breakpoints are candidates: sort them, or use weighted median

Weighted median: $\sum w_i|x-a_i|$ is minimised at any weighted median of the $a_i$. No search needed. In Manhattan geometry, solve $x$ and $y$ independently.