Searching for an extreme
Binary search finds a value in sorted data. Ternary search finds the extreme of a unimodal function, one that strictly increases to a single peak then strictly decreases, or the mirror for a single valley.
How it narrows
- Pick two probe points that split the current range into three roughly equal parts.
- Evaluate the function at both probes.
- Compare the two results: the side that is clearly worse cannot contain the extreme, so discard it.
- Repeat on the surviving two thirds.
Because each round removes about a third of the range, the interval shrinks steadily toward the extreme point.
Where it applies
- Tuning a single parameter where a quality measure rises then falls.
- Geometry problems where a distance is minimized at one point along a path.
- Any smooth single peaked landscape where you lack a clean derivative to follow.
Cautions
- The function must be genuinely unimodal; flats or extra bumps break the discard logic.
- For real inputs, stop when the interval is tiny rather than seeking an exact point.
Key idea
Ternary search brackets the single peak or valley of a unimodal function by repeatedly discarding the third that cannot hold the extreme.