Continuous Ternary Search

Continuous ternary search finds the maximum or minimum of a unimodal function defined over a real interval. It applies when the domain is continuous and the function has a single peak or valley.

Unlike the discrete version, there is no final scan. The algorithm stops when the interval becomes sufficiently small.

Problem

Given a function $f(x)$ defined over a real interval $[l, r]$ , find a point $x$ such that $f(x)$ is maximum.

Assume:

$f(x)$ increases up to some point $x^*$
then decreases afterward

Key Idea

Split the interval into three parts using two interior points:

m_1 = l + \frac{r - l}{3}, \quad m_2 = r - \frac{r - l}{3}

Evaluate:

If $f(m_1) < f(m_2)$ , the maximum lies in $[m_1, r]$
Otherwise, it lies in $[l, m_2]$

Repeat until the interval is small enough.

Algorithm

ternary_search_continuous(f, l, r, eps):
    while r - l > eps:
        m1 = l + (r - l) / 3
        m2 = r - (r - l) / 3

        if f(m1) < f(m2):
            l = m1
        else:
            r = m2

    return (l + r) / 2

Example

Consider:

f(x) = -(x - 2)^2 + 5

genui{“math_block_widget_always_prefetch_v2”:{“content”:“f(x)=-(x-2)^2+5”}}

The function has a maximum at:

x = 2

Running ternary search over an interval such as $[-10, 10]$ converges to this value.

Correctness

At each iteration, the algorithm discards one third of the interval while preserving the region that contains the maximum.

Because the function is unimodal:

If $f(m_1) < f(m_2)$ , the left third cannot contain the maximum
If $f(m_1) \ge f(m_2)$ , the right third cannot contain the maximum

The interval shrinks around the optimal point.

Termination

The algorithm stops when:

r - l \le \varepsilon

The returned value approximates the optimal point with error at most $\varepsilon$ .

Complexity

cost	value
iterations	$O(\log(\frac{r-l}{\varepsilon}))$
time	$O(T_f \cdot \log(\frac{r-l}{\varepsilon}))$
space	$O(1)$

Here $T_f$ is the cost of evaluating $f(x)$ .

Comparison

method	domain	requirement	result
discrete ternary search	integers	unimodal	exact index
continuous ternary search	real numbers	unimodal	approximate value

When to Use

Continuous optimization problems
Functions without closed form solutions
Simulation based optimization
Peak or minimum finding in real domains

Notes

Works for minimization by reversing the comparison
Precision depends on chosen $\varepsilon$
Floating point errors may affect convergence

Implementation

def ternary_search_continuous(f, l, r, eps=1e-9):
    while r - l > eps:
        m1 = l + (r - l) / 3
        m2 = r - (r - l) / 3
        if f(m1) < f(m2):
            l = m1
        else:
            r = m2
    return (l + r) / 2

func TernarySearchContinuous(f func(float64) float64, l, r, eps float64) float64 {
    for r-l > eps {
        m1 := l + (r-l)/3
        m2 := r - (r-l)/3

        if f(m1) < f(m2) {
            l = m1
        } else {
            r = m2
        }
    }
    return (l + r) / 2
}