Home/Learn/Ternary Search

Pattern Guide

Ternary Search

"Find minimum of unimodal function in O(log n). Divide range into thirds."

Ternary search finds the minimum (or maximum) of a unimodal function — one that decreases then increases (or vice versa) — in O(log n) evaluations. Divide the search range into thirds: evaluate at m1 and m2. If f(m1) > f(m2), minimum is in [m1, hi]; else in [lo, m2]. More useful than binary search when you cannot compute derivatives but can evaluate the function.

12 min readmath problems →

Problems you can solve with this pattern

4 problems · click any to start solving

All math →
1Minimum Distance to Target ElementEasySolve
2Peak Index in a Mountain ArrayMediumSolve
3Find in Mountain ArrayHardSolve
4Minimum Moves to Make Array ComplementaryMediumSolve
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 sign

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 sign
1
Minimum Distance to Target Element
Easy
Solve
2
Peak Index in a Mountain Array
Medium
Solve
3
Find in Mountain Array
Hard
Solve
4
Minimum Moves to Make Array Complementary
Medium
Solve
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.
← Z-Function & String MatchingTreap & Ordered Set →