# Discrete Ternary Search

# Discrete Ternary Search

Discrete ternary search finds the maximum or minimum of a unimodal function defined over integer indices. A function is unimodal if it strictly increases up to a point and then strictly decreases, or the reverse.

Unlike binary search, which relies on a monotone predicate, ternary search relies on a unimodal shape.

## Problem

Given a function $f(i)$ defined on integer indices $i \in [0, n-1]$, find an index $i$ such that $f(i)$ is maximum.

Assume:

$$
f(0) \le f(1) \le \dots \le f(k) \ge \dots \ge f(n-1)
$$

## Key Idea

Divide the interval into three parts using two midpoints:

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

Compare $f(m_1)$ and $f(m_2)$:

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

This reduces the search space.

## Algorithm

```id="dts-1"
ternary_search_discrete(f, l, r):
    while r - l > 3:
        m1 = l + (r - l) // 3
        m2 = r - (r - l) // 3

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

    best = l
    for i from l to r:
        if f(i) > f(best):
            best = i

    return best
```

## Example

Let

$$
f(i) = -(i - 4)^2 + 10
$$

The function increases up to $i = 4$ and decreases afterward.

f(i)=-(i-4)^2+10

The maximum occurs at $i = 4$.

## Correctness

At each step, the algorithm discards one third of the interval while preserving the region containing 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 remaining interval always contains the optimal point.

The final small interval is scanned directly to ensure correctness on discrete indices.

## Complexity

| phase      | cost        |
| ---------- | ----------- |
| iterations | $O(\log n)$ |
| final scan | $O(1)$      |
| total      | $O(\log n)$ |

Each iteration reduces the interval to about two thirds of its size.

Space:

$$
O(1)
$$

## Comparison

| method         | requirement        | time        |
| -------------- | ------------------ | ----------- |
| binary search  | monotone predicate | $O(\log n)$ |
| ternary search | unimodal function  | $O(\log n)$ |

Binary search finds boundaries. Ternary search finds extrema.

## When to Use

* Optimization over discrete domains
* Peak finding in unimodal arrays
* Problems where derivative information is unavailable

## Notes

* Final linear scan is necessary because indices are discrete
* Works for both maximum and minimum with condition reversal

## Implementation

```id="py-dts"
def ternary_search_discrete(f, l, r):
    while r - l > 3:
        m1 = l + (r - l) // 3
        m2 = r - (r - l) // 3

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

    best = l
    for i in range(l, r + 1):
        if f(i) > f(best):
            best = i

    return best
```

```id="go-dts"
func TernarySearchDiscrete(f func(int) int, l, r int) int {
    for r-l > 3 {
        m1 := l + (r-l)/3
        m2 := r - (r-l)/3

        if f(m1) < f(m2) {
            l = m1 + 1
        } else {
            r = m2 - 1
        }
    }

    best := l
    for i := l; i <= r; i++ {
        if f(i) > f(best) {
            best = i
        }
    }

    return best
}
```