Ternary Search

Why ternary search matters

Binary search answers "where is this value in a sorted list?" — but a huge class of problems asks something different: "where is the best value, when there is no target to look for?" You want the input that maximizes revenue, minimizes error, or hits the highest point of an arc, and you only have a function you can evaluate — not its derivative, not a closed form. When that function is unimodal (one hill, no false summits), ternary search finds the peak in a logarithmic number of evaluations without ever computing a gradient.

This makes it the go-to tool in three settings. In competitive programming, an astonishing number of problems reduce to "the answer is a single-peaked function of some parameter x" — minimize the time to meet a moving target, maximize the area under a constraint — and ternary search over x is the clean solution. In numerical optimization, it is the one-dimensional workhorse behind line searches: given a descent direction, you ternary-search the step size that minimizes the objective. In black-box tuning, where evaluating the function means running a simulation or training a model, it converges with far fewer probes than a linear scan.

How ternary search works, step by step

Suppose f is unimodal on [lo, hi] with a single maximum. The algorithm maintains the invariant that the peak always lies within the current [lo, hi]. Each iteration:

1. Split the interval into thirds by two interior probes:
   m1 = lo + (hi - lo)/3 and m2 = hi - (hi - lo)/3, so lo < m1 < m2 < hi.
2. Evaluate f(m1) and f(m2) — the two function calls that give the algorithm its name.
3. Compare and discard one outer third:
   • If f(m1) < f(m2), the function is still climbing at m2 relative to m1, so the peak lies to the right of m1. Set lo = m1 — the left third is gone.
   • If f(m1) > f(m2), the peak lies to the left of m2. Set hi = m2 — the right third is gone.
4. Repeat until hi - lo is smaller than a tolerance ε (continuous) or the window holds only a few elements (discrete). Return the midpoint of the final interval as the argmax.

Why discarding a third is safe. Because f is strictly unimodal, if f(m1) < f(m2) then no point in [lo, m1] can beat m2: to the left of the peak the function is strictly increasing, so everything below m1 is below f(m1) < f(m2). The peak therefore survives in [m1, hi]. The symmetric argument handles the other case. Each step removes exactly one third, so the surviving interval is 2/3 of the previous one.

Complexity: why it is O(log n)

After k iterations the interval width is (2/3)ᵏ times the original. To shrink an initial width W down to a tolerance ε you need

(2/3)^k · W ≤ ε   ⟹   k ≥ log(W/ε) / log(3/2) ≈ 1.71 · log₂(W/ε)

So the iteration count is Θ(log(W/ε)), or O(log n) for a discrete array of n elements. The base of the logarithm is 3/2, not 3: even though the interval is cut into three pieces, only one third is removed per step, so the useful "base" is 1 / (2/3) = 3/2. Because each step costs two evaluations, the total number of function calls is roughly 2 · log₁.₅ n ≈ 3.42 · log₂ n. Space is O(1) for the iterative form and O(log n) for the recursive form because of the call stack.

Ternary search vs binary search

The two are constantly confused, but they solve different problems. Binary search needs a monotonic predicate ("is the target ≥ this value?") and cuts the space in half with one comparison. Ternary search needs a unimodal function and locates a peak with two evaluations per step.

	Binary search	Ternary search	Golden-section search
What it finds	Target in a monotonic array / predicate boundary	Extremum of a unimodal function	Extremum of a unimodal function
Input requirement	Sorted / monotone	Strictly unimodal (one peak)	Strictly unimodal (one peak)
Evaluations per step	1 comparison	2 function calls	1 new function call (reuses one)
Interval shrink per step	1/2	2/3	≈ 0.618 (1/φ)
Steps to width ε	log₂(W/ε)	log₁.₅(W/ε) ≈ 1.71·log₂	log₁.₆₁₈(W/ε) ≈ 1.44·log₂
Time	O(log n)	O(log n)	O(log n)
Space	O(1)	O(1) iterative	O(1) iterative

A common student mistake is to reach for ternary search to look up a value in a sorted array — it works, but it is slower than binary search on that task: more comparisons per step and a slower shrink factor. Reserve ternary search for optimization, not lookup.

Continuous vs discrete ternary search

Continuous. Over a real interval you loop until hi - lo < ε, or — more robustly — you run a fixed number of iterations, say 200, chosen so that (2/3)²⁰⁰ is far below floating-point precision. The fixed-iteration form sidesteps the risk of an infinite loop from an ε too small to ever be reached in floating point.

Discrete. On an integer index range you must stop before m1 and m2 collide. A safe pattern is to loop while hi - lo > 2 using integer thirds, then linearly scan the final handful of indices. Equal adjacent values (a[m1] == a[m2]) break strict unimodality: with a plateau you cannot tell which third to drop, so guarantee strictness or fall back to a linear scan of the tie region.

Implementation in Python

# Continuous ternary search for the MAXIMUM of a unimodal function.
# Fixed iteration count avoids floating-point infinite loops.
def ternary_search_max(f, lo, hi, iterations=200):
    for _ in range(iterations):
        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3
        if f(m1) < f(m2):
            lo = m1          # peak is right of m1 — drop the left third
        else:
            hi = m2          # peak is left of m2 — drop the right third
    x = (lo + hi) / 2
    return x, f(x)


# Discrete ternary search: index of the peak of a bitonic (strictly
# increasing then strictly decreasing) array.
def peak_index(a):
    lo, hi = 0, len(a) - 1
    while hi - lo > 2:
        m1 = lo + (hi - lo) // 3
        m2 = hi - (hi - lo) // 3
        if a[m1] < a[m2]:
            lo = m1 + 1
        else:
            hi = m2 - 1
    # Scan the tiny remaining window directly.
    best = lo
    for i in range(lo + 1, hi + 1):
        if a[i] > a[best]:
            best = i
    return best


# Example: parabola peaks at x = 2.
print(ternary_search_max(lambda x: -(x - 2) ** 2 + 5, -10, 10))  # ~ (2.0, 5.0)
print(peak_index([1, 3, 7, 8, 6, 2]))                             # 3

For a minimum, flip the comparison to if f(m1) > f(m2), or simply search for the maximum of -f.

The golden-section variant

Naive ternary search wastes work: every iteration recomputes both probes from scratch, so f is evaluated twice per step even though the interval only shrank a little. Golden-section search fixes this by placing the two probes at the golden ratio φ = (√5 − 1)/2 ≈ 0.618 of the interval. The magic of φ is that after discarding one side, one of the two new probe points lands exactly where an old probe already was — so its function value can be reused, and each step costs only one new evaluation.

The interval shrinks by a factor of 0.618 per step instead of 0.667, and the per-step cost halves. When each call to f is expensive — a physical simulation, a model retrain — golden-section is the version you actually ship. Plain ternary search is the version you reach for when f is cheap and clarity matters more than a constant factor.

Common misconceptions and pitfalls

• Applying it to a non-unimodal function. This is the number-one bug. If f has two peaks, the comparison f(m1) vs f(m2) can point toward the smaller peak and permanently discard the third containing the true maximum. Ternary search gives no error — it silently returns a wrong answer. Prove unimodality first.
• Plateaus and equal values. Strict unimodality is required. If f(m1) == f(m2) on a flat region, neither third is provably safe to drop. In practice you must guarantee strictness or handle ties by scanning the tie window.
• The "base 3" fallacy. Cutting into three pieces does not give log base 3. You remove one third per step, keeping two — the interval shrinks by 2/3, so the base is 3/2. That is why ternary search needs more steps than binary search, not fewer.
• Floating-point termination. Looping until hi - lo < ε with a tiny ε can loop forever once the interval stops shrinking at machine precision. Prefer a fixed iteration count.
• Discrete off-by-one. With integer indices, failing to stop before m1 and m2 coincide (or overlap) causes an infinite loop or a skipped peak. Stop while the window is wide enough and finish with a linear scan.
• Reaching for it instead of calculus. If you can differentiate f and solve f'(x) = 0, or run gradient descent, those usually converge faster. Ternary search shines precisely when the derivative is unavailable or the function is a black box.