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
}