# Continuous Ternary Search

# 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

```id="cts-1"
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

```id="py-cts"
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
```

```id="go-cts"
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
}
```