Chapter 85

Home

Ternary Search

Binary search finds a point in a monotonic function. Ternary search finds the maximum (or minimum) of a unimodal function — one that increases then decreases (or vice versa). It's the continuous-optimisation analogue of binary search.

Ternary Search

C++ — ternary search on a unimodal function

double f(double x) { return -x * x + 5 * x + 3; }  // concave

double ternary_search(double lo, double hi, int iterations = 100) {
    for (int i = 0; i < iterations; i++) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2))
            lo = m1;  // max is to the right
        else
            hi = m2;  // max is to the left
    }
    return (lo + hi) / 2;  // approximate max
}

// O(iterations) — 100 iterations gives ~10⁻¹⁵ precision

💡 Integer ternary search

For integer domains, use while (hi - lo > 2) then evaluate the last few points directly. Avoid floating-point issues.

Key Takeaways