Ternary Search: Two Points to Nail Any Unimodal Peak in O(log n)

Binary search has one requirement: the function must be monotone. Go left, go right, done. But some functions rise to a single peak and fall away. You're looking for the top of a hill, not an item in a sorted list. Binary search can't help you. A single midpoint sample gives you an elevation. It doesn't give you a slope.

The ternary search algorithm solves this. Sample two interior points. Compare them. The unimodal property guarantees that one entire third of the search space is safe to discard. Repeat until the interval collapses. Logarithmic convergence, zero derivatives required.

It's the right tool when the problem gives you a single peak or valley and asks you to find it, or when you're optimizing a convex or concave function over a continuous range.

One Hill. That's the Whole Deal.

A function f is unimodal on [l, r] if there exists a unique point x* such that f strictly increases on [l, x*] and strictly decreases on [x*, r] (or the mirror image for a minimum). One peak. No plateaus. No second humps.

A unimodal function: one peak at x*, strictly monotone on each side. No exceptions.

An array qualifies if it strictly increases to some index then strictly decreases. [1, 4, 8, 12, 9, 5, 2] is unimodal with peak at index 3. LeetCode calls these "mountain arrays."

The strict-monotone requirement matters. A plateau anywhere in the search space breaks the elimination rule. If f is flat between two sample points, you get equal values and cannot determine which side holds the true peak. The algorithm will discard one of the thirds anyway. There is no error message.

Two Points Tell You Which Third to Drop

Pick two interior points m₁ and m₂, with l < m₁ < m₂ < r. The standard choice puts them at the one-third and two-thirds marks:

m₁ = l + (r - l) / 3
m₂ = r - (r - l) / 3

Evaluate f at both. The comparison gives you three cases:

f(m₁) < f(m₂)  →  peak is in [m₁, r]   →  drop the left third,  set l = m₁
f(m₁) > f(m₂)  →  peak is in [l, m₂]   →  drop the right third, set r = m₂
f(m₁) = f(m₂)  →  peak is in [m₁, m₂]  →  drop both outer thirds

After one iteration, the search space shrinks from (r − l) to (2/3)(r − l). After k iterations it is (2/3)^k × (r − l). Logarithmic convergence.

One comparison, one less third. The retained interval always contains the peak.

Why the Elimination Is Always Safe

Most explanations print the elimination rule, say "clearly," and move on. Let's do the contradiction instead.

Claim: if f(m₁) < f(m₂), the peak x* cannot lie in [l, m₁).

Proof by contradiction. Suppose x* ∈ [l, m₁). Then both m₁ and m₂ are strictly to the right of x*, which means both are in the decreasing region. Since f is strictly decreasing after x*, and m₁ < m₂, we must have f(m₁) > f(m₂). But our assumption says f(m₁) < f(m₂). Contradiction. So x* ∉ [l, m₁).

We can safely set l = m₁. The peak is still in the new interval.

The symmetric case works the same way. If f(m₁) > f(m₂), suppose x* ∈ (m₂, r]. Then both m₁ and m₂ are strictly left of x*, both in the increasing region. Since f is strictly increasing before x* and m₁ < m₂, we get f(m₁) < f(m₂). Contradicts our assumption. So x* ∉ (m₂, r], and we set r = m₂.

Both hypothetical placements lead to contradiction. The peak has nowhere to hide.

The proof requires that f is strictly monotone on each side of the peak. That is exactly the unimodal requirement. If f is not strictly monotone, the contradiction breaks down and the algorithm can discard the side that contains the true peak.

Why You Get O(log n)

The recurrence is T(n) = T(2n/3) + O(1), which Master Theorem resolves to Θ(log n). With a = 1, b = 3/2, and f(n) = O(1) = O(n⁰), we have n^(log_{3/2}(1)) = n⁰ = 1, matching f(n). This is the balanced case (case 2), giving T(n) = Θ(log n).

For the continuous version targeting precision ε on an interval of width R, the number of iterations needed is:

k ≥ log(R/ε) / log(3/2)  ≈  2.41 × log₂(R/ε)

With R = 1 and ε = 10⁻⁹, that is about 51 iterations. Competitive programmers use 200 iterations as a safe margin. The math says you need 51. The extra 149 are tradition at this point.

The Comparison Count Trap

Ternary search performs fewer iterations than binary search (log₃ n vs log₂ n), so it looks faster. But each ternary iteration requires two function evaluations, not one. The actual cost is:

Ternary:  2 × log₃(n)  ≈  1.26 × log₂(n)  comparisons
Binary:   1 × log₂(n)                       comparisons

For a sorted array, ternary search does roughly 26% more work than binary search. That is why binary search is preferred for sorted data. You added a midpoint and the algorithm got slower per n. Ternary search is not a faster binary search. It's a different tool for a different problem, one where binary search cannot decide direction from a single sample. Don't swap them.

When to Use Golden Section Search Instead

When f(x) is expensive to evaluate, there is a smarter variant. Standard ternary search computes two fresh evaluations per iteration. Golden section search reuses one evaluation. After the first iteration, one of the two new midpoints coincides with a previously evaluated point. You only pay for one new evaluation per step.

The convergence ratio improves too. Ternary search shrinks the interval by factor 2/3 ≈ 0.667 each step. Golden section search shrinks it by factor 1/φ ≈ 0.618, where φ = (1 + √5)/2. Yes, that golden ratio. The one from sunflowers and nautilus shells. It shows up here and cuts your evaluation count in half. For R = 1, ε = 10⁻⁹, that is about 44 iterations at one evaluation each, versus 51 × 2 = 102 evaluations for ternary. A 57% reduction in function calls.

Use ternary search when f(x) is cheap. Switch to golden section search when f(x) involves a simulation, a database query, or anything expensive.

One Structure, Every Language

Each implementation finds the peak index in a strictly unimodal integer array. The continuous variant just replaces integer bounds with float bounds and while lo < hi with while hi - lo > eps, using lo = m1 and hi = m2 instead of m1 + 1 and m2 - 1.

def ternary_search(arr: list[int]) -> int:
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        m1 = lo + (hi - lo) // 3
        m2 = hi - (hi - lo) // 3
        if arr[m1] < arr[m2]:
            lo = m1 + 1
        else:
            hi = m2 - 1
    return lo


# Continuous variant: find x that maximizes f on [lo, hi]
def ternary_search_max(f, lo: float, hi: float, eps: float = 1e-9) -> float:
    while hi - lo > eps:
        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3
        if f(m1) < f(m2):
            lo = m1
        else:
            hi = m2
    return (lo + hi) / 2

When the Ternary Search Algorithm Is the Right Tool

You have a function. You can call it. You cannot take its derivative, or the derivative is messy, or you just do not want to. If you can evaluate f(x) but cannot differentiate it, ternary search locates the maximum or minimum in O(log((r−l)/ε)) evaluations. No calculus required.

Peak and valley queries on bitonic arrays. Any array that increases then decreases has a unique peak. Any convex sequence has a unique minimum. Ternary search finds it in O(log n).

Convex optimization over a continuous interval. Many cost functions in algorithm problems are convex: total travel time as a function of meeting point, number of operations as a function of a parameter, error as a function of a threshold. Convex means unimodal, so ternary search applies directly.

Nested optimization. When f(x, y) is convex and you fix x, the resulting g(y) = f(x, y) is also unimodal. You can nest ternary searches: outer search over x, inner search over y. This gives O(log² n) per query on a 2D convex surface, which comes up in geometry and computational problems.

Nearest point on a parabola or curve. Given a point P and a convex curve, the distance from P to a point on the curve is a unimodal function of the curve's parameter. Ternary search finds the closest point without solving the system of equations.

Five Signals That Point to Ternary Search

1. The function is explicitly described as unimodal, convex, or concave.
2. The problem involves "find the peak" or "find the minimum" and the array is not sorted.
3. Brute force is O(n) or O(n²) over a 1D range and the answer is a single extremum.
4. The answer is a real number (not an index) and you need a precision of 10⁻⁶ or better.
5. The function value goes down-then-up or up-then-down as you move through the domain.

A non-signal: "find the maximum in an array." That's O(n) with a single scan and needs no search algorithm.

Worked Example 1: Peak Index in Mountain Array

Problem (LeetCode 852): An array arr of integers has exactly one peak. Find the peak index. Must run in O(log n).

Why it fits. The array is explicitly a mountain: strictly increasing to the peak, strictly decreasing after. That is the definition of unimodal. Ternary search applies directly.

# arr = [0, 4, 8, 12, 10, 7, 3, 1]
# Expected output: 3

def peakIndexInMountainArray(arr: list[int]) -> int:
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        m1 = lo + (hi - lo) // 3
        m2 = hi - (hi - lo) // 3
        if arr[m1] < arr[m2]:
            lo = m1 + 1   # peak is right of m1; discard left third
        else:
            hi = m2 - 1   # peak is left of m2; discard right third
    return lo

# Trace: lo=0, hi=7
#   m1=2 (arr[2]=8), m2=5 (arr[5]=7): 8 > 7, hi=4
# lo=0, hi=4
#   m1=1 (arr[1]=4), m2=3 (arr[3]=12): 4 < 12, lo=2
# lo=2, hi=4
#   m1=2 (arr[2]=8), m2=4 (arr[4]=10): 8 < 10, lo=3
# lo=3, hi=4
#   m1=3 (arr[3]=12), m2=4 (arr[4]=10): 12 > 10, hi=3
# lo=3=hi, return 3

Notice the trace eliminates the wrong third each time until the interval collapses at the peak.

Worked Example 2: Minimize Cost Over a Continuous Parameter

Problem: You are placing a warehouse along a 1D road. You have n stores at positions x[0]...x[n-1]. The total travel cost is f(p) = sum(|x[i] - p|) for all i. Find the optimal warehouse position p to minimize total distance. (The actual answer is the median, and you'd normally just sort. But f(p) is convex and the structure fits perfectly, so it's a clean warm-up before cases where no closed form exists.)

Why it fits. f(p) is a sum of absolute values, which is convex. A convex function has a unique minimum. Ternary search finds it.

def minimize_cost(positions: list[float]) -> float:
    lo, hi = min(positions), max(positions)

    def cost(p: float) -> float:
        return sum(abs(x - p) for x in positions)

    for _ in range(200):          # 200 iterations gives ~10^{-18} precision
        m1 = lo + (hi - lo) / 3
        m2 = hi - (hi - lo) / 3
        if cost(m1) > cost(m2):   # searching for minimum: reverse comparison
            lo = m1
        else:
            hi = m2

    return (lo + hi) / 2

# For minimum: flip the comparison (keep the side with the lower f value)
# For maximum: keep the side with the higher f value (as shown in other examples)

The comparison is reversed because we are minimizing. When cost(m1) > cost(m2), the left point has higher cost, so the minimum is not in the left third. Set lo = m1 to discard it. Symmetric to the maximum case.

Quick Recap

• What it is. A divide-and-conquer search for the extremum of a unimodal function, using two sample points per step.
• Core invariant. The peak always lies within the current [lo, hi] interval.
• Why it works. The unimodal property makes one third impossible by contradiction: if f(m₁) < f(m₂), a peak to the left of m₁ would force f(m₁) > f(m₂), which is false.
• Time. O(log n) discrete, O(log((r−l)/ε)) continuous. The recurrence T(n) = T(2n/3) + O(1) = Θ(log n).
• Space. O(1) iterative. O(log n) recursive.
• vs binary search. Ternary search does more total comparisons on sorted arrays (1.26× more). Use it only for unimodal functions, where binary search cannot decide direction from a single sample.
• Better variant. Golden section search reuses one evaluation per step and converges faster (factor 1/φ vs 2/3). Prefer it when f(x) is expensive.
• The one trap. A non-strictly-unimodal function (flat plateau, especially near the peak) can cause the algorithm to discard the correct region. Verify unimodality before applying.

If you are heading into a technical interview and want to practice recognizing when ternary search applies versus when binary search suffices, SpaceComplexity runs voice-based mock interviews with structured feedback on exactly this kind of pattern identification.

For the binary search foundation that ternary search builds on, including the off-by-one analysis that applies to discrete ternary search, see Binary Search: One Invariant to Rule the Search Space and Your Binary Search Has an Off-by-One Bug. For more cases where the obvious approach is not optimal and a search-on-answer pattern applies, see Five Coding Interview Problems Where Your First Solution Isn't Optimal.

Further Reading

• Ternary Search, cp-algorithms.com, complete reference with continuous and discrete implementations
• Optimizing Unimodal Functions, USACO Guide, competitive programming applications with worked problems
• Why is Binary Search Preferred Over Ternary Search?, GeeksforGeeks, the comparison count analysis
• Golden-section search, Wikipedia, the efficient variant that reuses evaluations
• Ternary Search, GeeksforGeeks, additional examples and the discrete implementation details