Ternary Search Fails on Non-Strictly 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).

Integer Stopping Criterion: Why Stop When hi - lo ≤ 2?

The integer stopping criterion is deceptively simple but often misused. The standard condition is while (hi - lo > 2). This ensures that the remaining range has at least 4 elements, because when hi - lo <= 2, we cannot safely compute two distinct midpoints — m1 and m2 might coincide or even cross each other due to integer division truncation. For example, if hi - lo = 2, then the range has 3 elements. Computed m1 = lo + (hi-lo)/3 = lo, m2 = hi - (hi-lo)/3 = hi. These are distinct (lo and hi) but there is no interior point; the algorithm would not have enough room to eliminate a third. So we stop and linearly scan the remaining 2 or 3 elements. If we used hi - lo >= 2, the loop would continue with a 3-element range, causing potential infinite loops or incorrect updates. In competitive programming, this subtlety is a frequent source of penalties. Always remember: stop when the range size is 3 or less, then brute force the survivor list.

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

Complexity Analysis and Real-World Applications

Each iteration reduces the search range to approximately 2/3 of its previous size. For a range of length n, the number of iterations needed is log_{3/2}(n) ≈ (log n) / (log 1.5) ≈ 1.71 * log2 n. So time complexity is O(log n), but with a higher constant than binary search.

Ternary search is not a replacement for binary search — they solve different problems. Binary search works on monotonic predicates; ternary search works on unimodal functions.

Time Complexity Derivation with Master's Theorem

To formally derive the time complexity, set up the recurrence relation. Each iteration of ternary search reduces the problem size from n to roughly 2n/3 (since we discard at least one third of the range) and performs O(1) work (calculating two midpoints, two function evaluations, and a comparison). Therefore:

T(n) = T(2n/3) + O(1)

This fits the form T(n) = a T(n/b) + f(n) with a = 1, b = 3/2, and f(n) = Θ(1) = Θ(n^0).

Compute n^(log_b a) = n^(log_{3/2} 1) = n^0 = 1.

Since f(n) = Θ(1) = Θ(n^0), we are in case 2 of the Master Theorem (f(n) = Θ(n^c) with c = log_b a). Therefore, T(n) = Θ(n^c log n) = Θ(1 * log n) = Θ(log n).

The base of the logarithm is 3/2, but in big-O notation the base is irrelevant. The important takeaway: ternary search runs in logarithmic time, with the constant factor determined by the base 3/2.

Golden Section Search: A More Efficient Variant

Golden Section Search is a variant designed for expensive function evaluations. Instead of choosing two new midpoints each iteration, it reuses one evaluation from the previous step by splitting the interval according to the golden ratio φ ≈ 1.618. The interval is divided so that the ratio of the larger part to the whole equals the ratio of the smaller part to the larger part: (a+b)/a = a/b = φ.

Initially we evaluate f(m1) and f(m2). In subsequent iterations, depending on which region is discarded, one of these points becomes the interior point of the new interval. For example, if f(m1) < f(m2) (min search), the new interval becomes [m1, hi] and m2 becomes the new lo? Actually, the new lo becomes m1, and the old hi stays. The new interior point is the old m1 (now at a position proportional to φ). So only one new evaluation is needed per iteration.

For production systems where each function call is costly (e.g., running a physics simulation), golden section search is the clear winner.

C++ Implementation of Integer Ternary Search

C++ mirrors the Java implementation but benefits from templates and the standard library. For integer arrays, we use int or long long depending on the index range. The same stop condition hi - lo > 2 and the linear scan of the remaining elements apply. The code below demonstrates both a function template for generic containers and a specialized version for std::vector<int>. Note that for continuous search, the same technique applies using double and a fixed iteration count or epsilon. Always be mindful of integer overflow when computing midpoints — use the idiom m1 = lo + (hi - lo) / 3 and m2 = hi - (hi - lo) / 3 to avoid overflow.

#include <iostream>
#include <vector>
#include <algorithm>

template<typename T>
int ternarySearchMax(const std::vector<T>& arr) {
    int lo = 0, hi = arr.size() - 1;
    while (hi - lo > 2) {
        int m1 = lo + (hi - lo) / 3;
        int m2 = hi - (hi - lo) / 3;
        if (arr[m1] < arr[m2])
            lo = m1 + 1;
        else if (arr[m1] > arr[m2])
            hi = m2 - 1;
        else {
            lo = m1 + 1;
            hi = m2 - 1;
        }
    }
    int maxIdx = lo;
    for (int i = lo + 1; i <= hi; ++i)
        if (arr[i] > arr[maxIdx])
            maxIdx = i;
    return maxIdx;
}

int main() {
    std::vector<int> arr = {1, 3, 5, 4, 2};
    std::cout << ternarySearchMax(arr) << std::endl;  // 2
    return 0;
}

Practice Problems to Master Ternary Search

Apply your understanding of ternary search with these curated problems from Codeforces and HackerEarth:

• [Codeforces 1357B](https://codeforces.com/problemset/problem/1357/B) — Ternary Search (explicit problem to implement the algorithm on a bitonic array)
• [HackerEarth: Ternary Search](https://www.hackerearth.com/practice/algorithms/searching/ternary-search/tutorial/) — Tutorial with multiple practice problems including Peak Finding
• [Codeforces 1185C2](https://codeforces.com/problemset/problem/1185/C2) — Exam in BerSU (ternary search on prefix sums)
• [LeetCode: Find Peak Element (bitonic variant)](https://leetcode.com/problems/find-peak-element/) — Classic problem that can be solved with ternary search or binary search on derivative.

Each problem reinforces the stop-condition nuance, and some require combining ternary search with greedy or prefix sums.