The idea
When the answer is a real number, binary search works the same way but never reaches lo == hi. Run a fixed number of iterations (100 is plenty) instead of testing a tolerance.
Ternary search finds the minimum of a function that first decreases and then increases. Evaluate it at two inner points m1 < m2: if f(m1) > f(m2) the minimum cannot lie left of m1; otherwise it cannot lie right of m2. A third of the range goes each step.
It appears when the quantity to minimise is a maximum or a sum of distances that shrinks, then grows.
Sample problem
852. Peak Index in a Mountain Array ↗ Medium
A mountain array strictly increases to a peak and then strictly decreases. Return the index of the peak in O(log n) time.
arr = [1,3,5,8,12,15,11,7,4,2] output = 5
Why the solution works
The array is unimodal: it goes up, then down. That is the shape ternary search is made for.
Probe two points m1 < m2. If the left value is smaller, m1 is on the rising side, so the peak cannot be at or before m1. Otherwise m2 is on the falling side, so the peak cannot be at or after m2. Either way a third of the range is discarded.
On an array a binary search on the slope (compare arr[mid] with arr[mid+1]) does the same job; ternary search is the version that also works for a function of a real variable, where there is no “next element”.
Complexity: O(log n) time, O(1) memory.
Watch out
- The function must be strictly unimodal. A flat stretch away from the minimum can send the search the wrong way.
- Prefer a fixed iteration count to
while (hi - lo > eps), which can loop forever on large values. - Print enough decimals, and never compare doubles with
==.