Ternary Search

Find the max or min of a unimodal function on a continuous interval in O(log(range/eps)).

[Binary Search]|

Jul 9, 2026

|explanatory_notes.md|

#ternary-search#unimodal#optimization#continuous

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;
using ld = long double;

ld ternaryMax(function<ld(ld)> f, ld l, ld r, int iter = 200) {
    for (int i = 0; i < iter; i++) {
        ld m1 = l + (r - l) / 3.0;
        ld m2 = r - (r - l) / 3.0;
        if (f(m1) < f(m2)) l = m1;
        else r = m2;
    }
    return (l + r) / 2.0;
}

ld ternaryMin(function<ld(ld)> f, ld l, ld r, int iter = 200) {
    for (int i = 0; i < iter; i++) {
        ld m1 = l + (r - l) / 3.0;
        ld m2 = r - (r - l) / 3.0;
        if (f(m1) > f(m2)) l = m1;
        else r = m2;
    }
    return (l + r) / 2.0;
}

23 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Ternary Search

Locates the maximum or minimum of a unimodal function over a continuous interval $[l, r]$ .

How It Works

Compute two interior points:

m_1 = l + (r-l)/3

m_2 = r - (r-l)/3

Compare

f(m_1)

and

f(m_2)

Eliminate one-third of the interval based on comparison

After

k

iterations, remaining interval has length

(2/3)^k \cdot (r-l)

Finding Maximum

f(m_1) < f(m_2)

: maximum is in

[m_1, r]

, set

l = m_1

Otherwise: maximum is in

[l, m_2]

, set

r = m_2

Finding Minimum

Flip the comparison, or negate

f

and use max version

When to Use

Unimodal functions (single peak or single valley)

Geometric optimization, distance minimization

When binary search needs a monotonic predicate but the function isn't monotonic

Complexity

200 iterations gives precision

\approx 10^{-35}

, far beyond double precision

Time —

O(\text{iterations} \cdot T(f))