Ternary Search, in depth: the unimodal invariant, integer and floating-point versions, golden-section search, and where it breaks

The invariant

Call f strictly unimodal on [l, r] for a minimum if there is a point x* such that f strictly decreases on [l, x*] and strictly increases on [x*, r]. Pick two points m1 < m2 inside the interval. There are two cases.

• If f(m1) < f(m2), then x* < m2. If x* were at or to the right of m2, both points would lie on the strictly decreasing side, which would force f(m1) > f(m2). The interval becomes [l, m2].
• If f(m1) > f(m2), then by the mirror argument x* > m1, and the interval becomes [m1, r].

If f(m1) = f(m2), strict unimodality puts x* strictly between them, so either update is safe. For a maximum, reverse every comparison. The invariant that the loop maintains is simple to state: x* is in [l, r]. Every correct variant on this page keeps it.

Placing m1 and m2 at the thirds, m1 = l + (r - l)/3 and m2 = r - (r - l)/3, means each step keeps two thirds of the interval in the worst case. The width therefore shrinks by a factor of 1.5 per step, which takes about log base 1.5 of (width / tolerance) steps. Some references, including the stub this page replaces, say log base 3. That would be true only if two thirds were discarded each time. The difference is real: going from a width of 10⁹ down to 10^-9 takes 103 steps, or 206 function evaluations.

Worked example by hand

Minimize f(x) = (x - 3)² + 1 on [0, 9]. The true minimum is at x = 3 with f = 1. Here are the first five steps, rounded to four decimals:

Step 1 lands m1 exactly on the minimum, but the algorithm cannot know that. It only learns that the minimum is left of 6. Step 2 is a tie, because 2 and 4 are equally far from 3. The code below moves l on ties, and the minimum stays inside, as the invariant promised. After five steps the width has gone from 9 to 1.1852, which is 9 x (2/3)⁵. Each step costs two evaluations, so this was ten evaluations for a factor of about 7.6.

The floating-point version

For a real-valued domain, run a fixed number of iterations rather than looping until r - l < eps. With floating-point numbers, an absolute epsilon smaller than the spacing of doubles near your values can never be reached. Near 10⁹, adjacent doubles are about 10^-7 apart, so a loop waiting for a width of 10^-9 spins forever. A fixed count always ends. Compute it from the width you start with and the tolerance you need, and add a margin.

import math

def ternary_min(f, lo, hi, tol=1e-9):
    """Minimize a strictly unimodal f on [lo, hi]. Returns x within about tol of the argmin."""
    if hi - lo <= tol:
        return (lo + hi) / 2
    steps = math.ceil(math.log((hi - lo) / tol) / math.log(1.5)) + 2
    for _ in range(steps):
        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3
        if f(m1) < f(m2):
            hi = m2
        else:              # ties move lo; safe only because f is strictly unimodal
            lo = m1
    return (lo + hi) / 2

assert abs(ternary_min(lambda x: (x - 3) ** 2 + 1, 0, 9) - 3) < 1e-6

There is also a floor on accuracy that no iteration count removes. Near a smooth minimum, f(x* + d) - f(x*) grows like d². Once d² times the curvature falls below the rounding error of f, the two values compare at random. As a result, you can locate a smooth minimum only to about the square root of machine epsilon, around 10^-8 relative to the scale of x. Asking for 10^-12 wastes evaluations and returns noise. If you need the minimum value, that is far more accurate than the location, because the function is flat there.

The integer version, and a better alternative

On integers, the thirds have to be rounded, and the interval stops shrinking once it is small, so the loop needs a different stopping rule. Because x* is never at m2 when f(m1) < f(m2), you can also drop m2 itself, which gives r = m2 - 1. Symmetrically, l = m1 + 1 when f(m1) >= f(m2). Stop when at most three candidates remain and scan them.

def ternary_min_int(f, lo, hi):
    """Index of the minimum of a strictly unimodal f on the integers lo..hi inclusive."""
    while hi - lo > 2:
        m1 = lo + (hi - lo) // 3
        m2 = hi - (hi - lo) // 3
        if f(m1) < f(m2):
            hi = m2 - 1
        else:
            lo = m1 + 1
    return min(range(lo, hi + 1), key=f)

c = [9, 7, 4, 2, 1, 3, 6, 8, 11, 15]
assert ternary_min_int(c.__getitem__, 0, len(c) - 1) == 4

Tracing the array: [0, 9] probes indices 3 and 6 (values 2 and 6) and keeps [0, 5]. Then indices 1 and 4 (values 7 and 1) give [2, 5]. Then indices 3 and 4 (values 2 and 1) give [4, 5], and the scan returns index 4. The hi - lo > 2 guard matters most in the variant without the -1 and +1. There, once the width is 2 or less, (hi - lo) // 3 is 0, so m1 equals lo and lo = m1 never moves.

On integers there is a simpler option that is usually better: binary search for the first index i where f(i) < f(i + 1). For a strictly unimodal f, the predicate f(i) < f(i + 1) is false before x* and true from x* on. That turns the problem into a binary search on a monotone predicate, which halves the interval for two evaluations per step instead of keeping two thirds.

def unimodal_min_bsearch(f, lo, hi):
    while lo < hi:
        mid = (lo + hi) // 2
        if f(mid) < f(mid + 1):
            hi = mid          # rising at mid: the minimum is at mid or to its left
        else:
            lo = mid + 1      # falling at mid: the minimum is to its right
    return lo

Golden-section search: reuse one probe

Ternary search throws away work. After each step, one of the two probes lies inside the new interval, but its value is never reused. Golden-section search places the probes so that the surviving probe sits exactly where the next step needs it. The positions use the golden ratio, with probes at l + 0.382(r - l) and l + 0.618(r - l). Each step then costs one new evaluation and shrinks the width by a factor of about 1.618.

INV_PHI = (5 ** 0.5 - 1) / 2          # 0.618...

def golden_min(f, lo, hi, steps=100):
    a, b = lo, hi
    x1, x2 = b - INV_PHI * (b - a), a + INV_PHI * (b - a)
    f1, f2 = f(x1), f(x2)
    for _ in range(steps):
        if f1 < f2:                     # minimum in [a, x2]; old x1 becomes new x2
            b, x2, f2 = x2, x1, f1
            x1 = b - INV_PHI * (b - a)
            f1 = f(x1)
        else:                           # minimum in [x1, b]; old x2 becomes new x1
            a, x1, f1 = x1, x2, f2
            x2 = a + INV_PHI * (b - a)
            f2 = f(x2)
    return (a + b) / 2

Per evaluation, the comparison is clear. Ternary search shrinks the width by the square root of 1.5, about 1.22, while golden-section search shrinks it by 1.618. For the 10⁹ to 10^-9 example that means 87 evaluations instead of 206. When f is cheap, as in a programming contest, the difference rarely matters, and ternary search is easier to get right. When each evaluation is a simulation, a backtest or a training run, use golden-section search. Its one subtlety is that rounding slowly moves the reused probe away from the exact golden position, so library versions recompute probes from the endpoints every so often.

Where it breaks

Everything above depends on strict unimodality, and real functions often lack it. There are three ways it fails.

Plateaus. Take the array [5, 1, 5, 5, 5, 5, 5, 5, 5, 5]. The integer version probes indices 3 and 6, sees a tie and moves right, losing the minimum at index 1. Mirror the array and the opposite tie rule fails instead. No tie-breaking rule can work, because with a flat region the minimum can be left of m1, between the probes or right of m2, and two equal values cannot tell these cases apart. If your function can be flat, for example because it is integer-valued, rounded or clipped, ternary search is unsafe. Only a tie-breaking key that makes the function strictly unimodal again, or a scan, will do.

Several local minima. The method returns some local minimum, with no warning that a better one exists elsewhere. If you cannot prove the shape, sample a coarse grid first, then refine around the best grid point.

Noise. If f is measured, such as latency at a given batch size or validation loss at a given learning rate, two runs at the same point disagree. A single unlucky comparison discards the third that holds the true optimum, and nothing later can recover it. Average several runs per probe, or use a method built for noisy objectives, as described in Hyperparameter Optimization Architecture.

Two facts help when you need a proof of shape. A convex function is unimodal, and it is strictly unimodal if it is strictly convex. Sums and maxima of convex functions are convex. For example, the distance between two points moving at constant velocity is convex in time, so the time of closest approach of a whole set of moving points, measured by the maximum pairwise distance, is a valid target. Most correct contest uses of ternary search come down to one of these two arguments.

Two dimensions: nested searches

For a function of two variables that is jointly convex, g(x) = min over y of f(x, y) is convex in x. You can therefore nest searches: the outer search over x calls an inner search over y for each probe.

def min_2d(f, x_lo, x_hi, y_lo, y_hi):
    def g(x):
        y = ternary_min(lambda y: f(x, y), y_lo, y_hi)
        return f(x, y)
    x = ternary_min(g, x_lo, x_hi)
    return x, ternary_min(lambda y: f(x, y), y_lo, y_hi)

The cost multiplies, because the inner search runs for every outer probe. On a domain of width 10 with the default tolerance, each level makes about 120 evaluations, so the whole search makes roughly 14,000 evaluations of f. That is fine for a closed-form f and hopeless for an expensive one. Joint convexity is required. A function convex in x for each fixed y and in y for each fixed x can still have a non-convex g. Past two or three dimensions, gradient methods are the right tool, as covered in Gradient Descent.

Choosing a method

All of these share the divide-and-conquer pattern of discarding part of the input with a constant-time test, described in Divide and Conquer. Ternary search is the version where the test is a comparison of two function values.

What to do next

• Implement ternary_min and ternary_min_int from memory, then test them against brute force on 1,000 random strictly unimodal arrays and functions.
• Feed the integer version the plateau array [5, 1, 5, 5, 5, 5, 5, 5, 5, 5] and watch it fail, so you remember why strictness matters.
• Replace one epsilon-based loop in your code with a fixed iteration count computed from the width and tolerance.
• Implement golden-section search and count evaluations against ternary search on the same function.
• Before using either on a real objective, write down why it is unimodal, for example because it is convex or a sum or maximum of convex terms. If you cannot, grid-sample first.
• Solve one closest-approach problem with moving points to practise the convexity argument.