Unimodal functions
A function is unimodal on an interval if it rises to a single peak and then falls, with no other bumps. Binary search needs a sorted yes or no boundary, but a hump has no such boundary, so we need a different idea.
Probing two interior points
Ternary search picks two points inside the current interval that split it into roughly three equal pieces. Compare the function values at those two points:
- If the left point is lower, the peak cannot be in the leftmost third, so discard it.
- If the right point is lower, the peak cannot be in the rightmost third, so discard it.
Either way the interval shrinks toward the peak. Repeat until the interval is tiny, then report any point inside as the maximum.
Where it applies
The same routine finds a minimum of a valley shaped function by flipping the comparisons. It works on continuous ranges with a stopping tolerance, and on integer ranges with a small final scan. It does not work on functions with several humps, since a local probe can be fooled.
Key idea
For a single hump function, two interior probes let you discard one outer third each round, converging on the peak.