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

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

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

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
}