Pattern Reference
Ternary Search
"Find peak of unimodal function. Divide into three parts, discard one. Bitonic arrays, convex functions."
Loading...
Deep Dive Tutorial
Ternary search requires the function to be strictly unimodal: it decreases from lo to some peak/valley, then increases (or decreases) to hi. At each step, evaluate at 1/3 and 2/3 of the interval. The worse side is eliminated. After O(log_{3/2}(range/eps)) steps, converge to the answer. For discrete domains, 100 iterations of continuous ternary search is overkill — use binary search on the derivative instead when possible.
Ternary search templates — continuous and discrete
// Continuous ternary search — find x minimizing f(x) in [lo, hi]
function ternarySearchMin(lo, hi, f, iterations = 200) {
for (let i = 0; i < iterations; i++) {
const m1 = lo + (hi - lo) / 3;
const m2 = hi - (hi - lo) / 3;
if (f(m1) < f(m2)) hi = m2;
else lo = m1;
}
return (lo + hi) / 2;
}
// Discrete ternary search — integer domain
function ternarySearchDiscrete(lo, hi, f) {
while (hi - lo > 2) {
const m1 = lo + Math.floor((hi - lo) / 3);
const m2 = hi - Math.floor((hi - lo) / 3);
if (f(m1) <= f(m2)) hi = m2;
else lo = m1;
}
// Check remaining candidates
let best = lo;
for (let x = lo; x <= hi; x++) if (f(x) < f(best)) best = x;
return best;
}
// Alternative for discrete: binary search on derivative
// If f is unimodal with integer domain, f(x) - f(x-1) changes sign once
// Binary search for where derivative flips signWorked Problems
telescope
When to use ternary search vs binary search:
- Binary search: function is monotone (strictly increasing or decreasing) → O(log n)
- Ternary search: function is unimodal (one peak/valley) → O(log n)
- Binary search on derivative: f'(x) changes sign once → more natural for discrete domains
Pitfall: Ternary search requires strictly unimodal function. If there's a flat region at the peak, ternary search may not converge correctly.
Practical alternatives for discrete unimodal: binary search on f(x) ≤ f(x+1) (slope). Simpler and fewer iterations than ternary search for integers.
- Binary search: function is monotone (strictly increasing or decreasing) → O(log n)
- Ternary search: function is unimodal (one peak/valley) → O(log n)
- Binary search on derivative: f'(x) changes sign once → more natural for discrete domains
Pitfall: Ternary search requires strictly unimodal function. If there's a flat region at the peak, ternary search may not converge correctly.
Practical alternatives for discrete unimodal: binary search on f(x) ≤ f(x+1) (slope). Simpler and fewer iterations than ternary search for integers.