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.