1. One-Liner
Ternary search shrinks a unimodal interval (single peak or valley) by sampling at two points that split the range into three parts and discarding the third where the optimum cannot lie.
2. The Problem It Solves
Find the maximum (or minimum) of a unimodal function on [L, R]—discrete array or continuous function—using fewer assumptions than binary search on a sorted array (which targets equality).
3. The Core Idea
If f(mid1) < f(mid2) for a max problem, the peak lies to the right of mid1; else it lies to the left of mid2. Each iteration removes ~⅓ of the domain.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | While R - L > 2 (discrete) or > ε (continuous). |
| 2 | m1 = L + (R-L)/3, m2 = R - (R-L)/3. |
| 3 | Compare f(m1) and f(m2); shrink [L,R] accordingly. |
| 4 | Scan leftover few points for discrete max. |
5. Dry Run Example
Discrete array (unimodal max): [1, 3, 8, 7, 4], indices 0..4.
| Iter | L | R | m1 | m2 | f(m1) | f(m2) | Keep |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 4 | 1 | 3 | 3 | 7 | peak right of m1 → L = 2? Standard rule: if f(m1) < f(m2) then L = m1+1 else R = m2-1 — adjust per variant. |
After convergence, maximum 8 at index 2.
6. Key Properties
| Property | Detail |
|---|---|
| Needs | Unimodality (one peak). |
| Time | O(log n) discrete; constant factor > binary on derivatives. |
| Use | Convex optimization discretizations, competitive programming. |
7. Where It Is Used
| Company / domain | Use |
|---|---|
| ML / numerics | Line search approximations, golden section cousin. |
| Games | Projectile peak height, parabolic curves on grids. |
8. Interview Tips
State unimodal clearly. Compare ternary vs binary on sorted array (different problem). For real-valued functions, mention precision loop or golden-section alternative.
9. Comparison with Other Algorithms
| Method | When |
|---|---|
| Binary search | Monotone predicate / sorted equality. |
| Ternary | Unimodal objective, no gradient. |
| Golden section | Fewer evaluations, similar goal. |
10. Complexity
| Discrete | Continuous |
|---|---|
| O(log n) per iteration ~⅓ reduction | O(log((R-L)/ε)) typical |
| O(1) space | O(1) space |
Implementation Example (PYTHON)
def ternary_search_max(arr):
"""Max index in unimodal arr (strictly inc then dec)."""
lo, hi = 0, len(arr) - 1
while hi - lo > 2:
third = (hi - lo) // 3
m1 = lo + third
m2 = hi - third
if arr[m1] < arr[m2]:
lo = m1
else:
hi = m2
return max(range(lo, hi + 1), key=lambda i: arr[i])