Don't memorize ternary search — watch the window shrink. When a curve rises to a single peak and falls, two probes at the one-third marks are enough to know which outer third cannot hold the top. Throw that third away, keep two-thirds, repeat. The window collapses onto the peak in O(log n). It is binary search's cousin — but it needs a unimodal shape, not a monotonic one.
The curve has a single peak at x = 7. The amber band is the live window [lo, hi]. Press Step: two probes appear at the thirds, and the third that cannot hold the peak turns red and is dropped.
m1 = lo + (hi − lo)/3 m2 = hi − (hi − lo)/3
12.0
Window width
—
Peak x ≈
Two probes beat one midpoint
Binary search works because the data is monotonic: check the middle, and one comparison rules out an entire half. A unimodal curve breaks that — the middle might be on the way up or on the way down, and a single value cannot tell you which. So ternary search takes two samples, m1 at the one-third mark and m2 at the two-third mark. If f(m1) < f(m2), the peak cannot lie left of m1 (the curve is still climbing toward m2), so you set lo = m1 and drop the left third. If f(m1) > f(m2), symmetric: set hi = m2. Either way two-thirds survives, and the window keeps closing on the maximum.
01
Require a single peak
The function (or bitonic array) must rise then fall exactly once. On arbitrary data ternary search is meaningless.
02
Probe at the thirds
m1 = lo + (hi − lo)/3, m2 = hi − (hi − lo)/3. Evaluate f at both.
03
Drop the losing third
For a max: if f(m1) < f(m2) set lo = m1; else set hi = m2. The discarded third can't contain the peak.
04
Shrink to a sliver
Each step keeps ~2/3 of the range, so after O(log n) iterations lo and hi meet on the peak.
Time
O(log n)
Space
O(1)
Needs
Unimodal
Per step
2 evals
The window shrinks by a factor of 2/3 each iteration, so the count of steps grows like log base 1.5 of n — the same logarithmic class as binary search, just with two function evaluations per step instead of one. Reach for ternary search whenever you are optimizing a unimodal quantity: the peak of a projectile, the best meeting point on a line, or the minimum of a convex cost. When the data is merely sorted or a predicate is monotonic, plain binary search is the simpler, faster tool.
SOLVE IT YOURSELF
Solve it: find the peak
This one is yours to write — in Python or TypeScript, running for real in your browser. Edit the stub below, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.
YOUR TASK
A bitonic array strictly increases, then strictly decreases. Implement peak_index(nums): return the index of the maximum using ternary search — split the range into thirds with two probes and drop the third that cannot hold the peak. O(log n).
HINTS — 4 IDEAS
Keep a window [lo, hi]. Take two probes at the thirds: m1 = lo + (hi−lo)//3 and m2 = hi − (hi−lo)//3.
If nums[m1] < nums[m2] you are still climbing at m1, so the peak is to its right: lo = m1 + 1.
Otherwise the peak is at or left of m2: hi = m2 − 1. (Using m2 − 1, not m2, keeps the window shrinking.)
When lo == hi the window is one element — that index is the peak.
CPython · WebAssembly✓ Solved
1
1
Check yourself
1 · What property must the function have for ternary search to work?
Ternary search needs exactly one extremum: the curve rises then falls (max) or falls then rises (min). That is what makes a third safe to drop.
2 · Searching for a maximum, you find f(m1) < f(m2). What do you do?
Since m2 is higher, the curve is still climbing past m1, so the peak is to the right of m1. The left third [lo, m1] can be discarded: lo = m1.
3 · Why can't you just use binary search here?
Binary search relies on a monotonic order. A unimodal curve isn't monotonic, so one comparison at the middle is ambiguous — you need two probes to read the slope.
Questions
Ternary vs binary search — which is faster?
Same big-O class. Binary search keeps 1/2 with one evaluation per step; ternary keeps 2/3 with two evaluations. So ternary needs a few more iterations and twice the evals per iteration — a constant-factor cost, not an asymptotic one. Use it only when the data is unimodal rather than monotonic.
How do I handle an integer domain?
The 1/3 splits can stall on the last two or three integers because of rounding. A safe pattern is to loop while (hi − lo > 2) and then check the remaining handful directly, or compare f(mid) with f(mid + 1) to decide which half of the integer range keeps climbing.
Can it find a minimum too?
Yes — for a convex, single-valley function just flip the comparison: keep the side with the smaller value. The structure is identical; only the direction of the test changes.
Two probes, and the peak has nowhere to hide.
Split into thirds, drop the third that can't win, keep two-thirds — the window closes on the maximum in log time.