Ternary Search Algorithm — Finding Extrema in Unimodal Functions

Most engineers encounter binary search early and carry it like a trusty Swiss Army knife for the rest of their careers. But there's a whole class of problems — optimizing a physics simulation, tuning a cost function, finding the peak throughput of a network — where binary search simply can't help, because the data isn't sorted in the classical sense. It rises to a peak and then falls, forming a shape mathematicians call unimodal. Ternary search was designed exactly for this shape, and understanding it unlocks a family of optimization problems that would otherwise require calculus or brute-force scanning.

The core problem ternary search solves is this: given a unimodal function f(x) over a continuous or discrete domain, find the value of x that maximizes (or minimizes) f(x), without evaluating the entire domain. Binary search needs a sorted, monotonic sequence to compare against a target. Ternary search instead compares the function's output at two interior probe points — m1 and m2 — to decide which third of the search space cannot contain the optimum. Each iteration shrinks the search space to two-thirds of its previous size, converging on the answer exponentially fast.

By the end of this article you'll be able to implement both the iterative and recursive flavours of ternary search in Java, articulate exactly why it converges in O(log₃ n) iterations, know when to prefer it over binary search or golden-section search, avoid the three most common implementation bugs that cause infinite loops or missed answers, and answer the ternary search questions that show up in FAANG-level interviews. Let's build this from first principles.

What is Ternary Search? — Plain English

Ternary search finds the minimum or maximum of a unimodal function — a function that has exactly one peak (for maximum search) or one valley (for minimum search). Unlike binary search which requires a sorted array, ternary search works on unimodal functions: the function increases then decreases (for max) or decreases then increases (for min). The algorithm divides the current range into three equal parts using two midpoints m1 and m2. Comparing f(m1) and f(m2) eliminates one-third of the range: if f(m1) < f(m2), the maximum cannot be in [lo, m1]; if f(m1) > f(m2), the maximum cannot be in [m2, hi]. This continues until the range is small enough.

How Ternary Search Works — Step by Step

Ternary search for maximum of unimodal function f on range [lo, hi]:

1. While hi - lo > epsilon (or for integers, while hi - lo > 2):
2. a. m1 = lo + (hi - lo) / 3.
3. b. m2 = hi - (hi - lo) / 3 (equivalently, lo + 2*(hi-lo)/3).
4. c. If f(m1) < f(m2): maximum is not in [lo, m1-1] → set lo = m1 + 1.
5. d. If f(m1) > f(m2): maximum is not in [m2+1, hi] → set hi = m2 - 1.
6. e. If f(m1) == f(m2): maximum is in [m1+1, m2-1] → lo = m1+1, hi = m2-1.
7. Check remaining elements in [lo, hi] for the maximum.

For minimum search, reverse the comparisons: if f(m1) > f(m2), minimum is not in [lo, m1-1].

Worked Example — Finding Maximum in Array [1,3,5,4,2]

Array: [1,3,5,4,2], indices 0-4. Maximum is at index 2 (value 5).

Round 1: lo=0, hi=4. m1=0+(4-0)/3≈1, m2=4-(4-0)/3≈2 (integer: m1=1, m2=3). f(m1)=arr[1]=3, f(m2)=arr[3]=4. f(m1)<f(m2) → maximum not in [0,m1]=[0,1] → lo=m1+1=2.

Round 2: lo=2, hi=4. m1=2+(4-2)/3≈2, m2=4-(4-2)/3≈3 (m1=2, m2=3). f(m1)=arr[2]=5, f(m2)=arr[3]=4. f(m1)>f(m2) → maximum not in [m2+1,hi]=[4,4] → hi=m2-1=2.

Round 3: lo=2, hi=2. hi-lo=0 <= 2 threshold. Check [2,2]: arr[2]=5. Maximum at index 2.

Each round eliminates ~1/3 of remaining range. Total iterations: O(log_1.5(n)) ≈ O(log n).

Implementation

Ternary search divides the range into thirds using two probe points. The implementation handles both discrete (integer index) and continuous (floating-point) variants. For continuous optimization, iterate until hi-lo < epsilon (e.g., 1e-9). For integer arrays, iterate until hi-lo <= 2 and check remaining elements directly. Ternary search is less common than binary search because it requires unimodal functions, but it is essential for competitive programming problems involving bitonic arrays or geometric optimization.

def ternary_search_max_array(arr):
    """Find index of maximum in unimodal array."""
    lo, hi = 0, len(arr) - 1
    while hi - lo > 2:
        m1 = lo + (hi - lo) // 3
        m2 = hi - (hi - lo) // 3
        if arr[m1] < arr[m2]:
            lo = m1 + 1
        elif arr[m1] > arr[m2]:
            hi = m2 - 1
        else:
            lo, hi = m1 + 1, m2 - 1
    return max(range(lo, hi + 1), key=lambda i: arr[i])

def ternary_search_min_continuous(f, lo, hi, iterations=200):
    """Find x in [lo,hi] that minimizes f (unimodal, continuous)."""
    for _ in range(iterations):
        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3
        if f(m1) < f(m2):
            hi = m2
        else:
            lo = m1
    return (lo + hi) / 2

# Discrete: find max of [1,3,5,4,2]
print(ternary_search_max_array([1,3,5,4,2]))  # 2 (index)

# Continuous: minimize (x-3)^2 on [0,10]
f = lambda x: (x - 3) ** 2
print(round(ternary_search_min_continuous(f, 0, 10), 6))  # ~3.0

Frequently Asked Questions