Searching a Unimodal Function

You're handed a function you can only evaluate point by point (no formula, no derivative) and told it's unimodal on an interval, it strictly increases, hits one peak, then strictly decreases, with no other bumps. Where's the peak? Checking every point is wasteful. The right tool is a cousin of binary search, adapted for a peak instead of a sorted target: ternary search.

Why two probe points are enough

Pick two points $m_1 < m_2$ inside the current interval $[lo, hi]$, evenly spaced so they split it into thirds. Because the function is unimodal, comparing $f(m_1)$ and $f(m_2)$ tells you which third of the interval can be safely thrown away:

• If $f(m_1) < f(m_2)$, the peak cannot lie to the left of $m_1$, the function is still climbing at $m_1$ (or the peak is between $m_1$ and $m_2$), so discard $[lo, m_1)$ and search $[m_1, hi]$.
• If $f(m_1) > f(m_2)$, symmetric reasoning discards $(m_2, hi]$ and you search $[lo, m_2]$.

In plain English: two probes are enough to identify which side is "still going uphill," and unimodality guarantees the peak must be on that side or between the probes, never on the strictly-downhill side you just discarded. Each round shrinks the interval to two-thirds of its previous size, so after $k$ rounds the interval is $(2/3)^k$ of its original width, shrinking to arbitrary precision in a number of steps that grows only logarithmically with how precise you need to be.

Worked example: finding the peak of $f(x) = -(x-4)^2 + 10$ on $[0, 10]$

This is unimodal with true peak at $x=4$. Round 1: $lo=0, hi=10$, probes $m_1 = 3.33$, $m_2=6.67$. $f(3.33) = -(0.67)^2+10\approx9.55$, $f(6.67)=-(2.67)^2+10\approx2.87$. Since $f(m_1) > f(m_2)$, discard the right third: new interval $[0, 6.67]$. Round 2: $lo=0,hi=6.67$, probes $m_1=2.22, m_2=4.44$. $f(2.22)=-(1.78)^2+10\approx6.83$, $f(4.44)=-(0.44)^2+10\approx9.80$. Now $f(m_1) < f(m_2)$, so discard the left third: new interval $[2.22, 6.67]$. Notice the true peak, $x=4$, is inside $[2.22,6.67]$ at every step, after just two rounds the search window has already shrunk from width 10 to width 4.44, and it keeps shrinking by a factor of $2/3$ every round from here.

Adjust the curve and imagine dropping two probe points inside the visible window: comparing their heights always tells you which side to discard, because a single-peaked curve can never have its true maximum on the strictly-descending side of either probe.

What this means in practice

Ternary search is the go-to technique whenever an interview question describes a "one hump" relationship, profit that rises then falls as you increase price, accuracy that rises then falls as you tune a single hyperparameter, PnL that rises then falls with position size, and you need the optimal point using few evaluations, especially when each evaluation is expensive (a backtest run, a live query). It generalizes the "cut the search space in half" instinct from binary search to "cut it to two-thirds," using a comparison of function values instead of a comparison against a fixed target.