Ternary Search

Ternary search is the divide-and-conquer cousin of Binary Search for unimodal functions — those with a single peak (maximum) or single valley (minimum) — defined over either a discrete index range or a continuous interval. At each step, ternary search partitions the candidate range into three parts via two probes, compares the function values at the two probes, and uses the comparison to discard one of the outer thirds, since the discarded third cannot contain the extremum. The cost is O(log_{3/2} n) — the same big-O class as binary search but with a worse constant factor (roughly 2 × log_2(3/2) ≈ 1.18 times more comparisons per element discarded). The key fact about ternary search is what it solves that binary search can’t: binary search needs a monotone predicate (a function that’s false then true); ternary search needs only unimodality (a function that’s increasing then decreasing, or vice versa). When the problem is finding an extremum of a continuous unimodal function — common in numerical optimization — ternary search (or its sibling golden-section search) is the right tool. When the input is a sorted array, Binary Search beats ternary on every axis and there’s no reason to use ternary.

1. Intuition — Climbing a Hill in the Fog

Imagine standing at the bottom of a single, smooth hill in dense fog. You can’t see the summit, but you can stand at any point and instantly check your altitude. Your job: find the highest point.

If you knew the altitude function was strictly increasing then decreasing (a single peak), here’s a strategy that doesn’t require seeing the hill: pick two points roughly one-third and two-thirds of the way along the path. Measure altitudes at both.

• If altitude at the one-third point is lower than at the two-thirds point, the peak cannot be in the leftmost third — because the function is rising as you move from one-third to two-thirds, so it must have been rising at every point to the left of one-third too. Discard the leftmost third; recurse on [1/3, end].
• If altitude at the one-third point is higher than at the two-thirds point, the peak cannot be in the rightmost third, by a symmetric argument. Discard the rightmost third; recurse on [start, 2/3].
• If they’re equal (rare in continuous functions, common in discrete), discard one of the outer thirds — either is safe.

Each step shrinks the search interval by a factor of 2/3 (you keep 2/3 of it). After k steps the remaining interval has size (2/3)^k × initial_size. To reduce a range of size n down to a single position, you need k such that (2/3)^k × n ≤ 1, i.e., k ≥ log_{3/2} n. That’s the cost.

The crucial precondition is unimodality: the function increases up to one point, then decreases (or vice versa). With no monotone structure at all — a function with multiple peaks — ternary search returns garbage, exactly like binary search returns garbage on unsorted data. With a fully monotone function, ternary search still works but is strictly worse than binary search; the third probe buys you nothing because monotonicity is a stronger condition than unimodality and binary search exploits it more efficiently.

The contrast with binary search is sharp. Binary search asks “is the answer to the left or to the right of mid?” — one comparison, half the range discarded. Ternary search asks “is the answer in the left third, the middle third, or the right third?” — but the comparison structure forces two function evaluations to make the call, and only one outer third is discarded each step (the middle third is kept). You pay 2 evaluations per step to discard 1/3 of the range, where binary search pays 1 evaluation per step to discard 1/2. The arithmetic of “evaluations per bit of progress” gives binary search ~30% fewer evaluations than ternary, even ignoring the worse base of the logarithm.

2. Tiny Worked Example — Discrete Unimodal Array

Take the array arr = [1, 3, 7, 12, 15, 14, 10, 8, 4, 2] (length 10). It strictly increases through index 4 (value 15) then strictly decreases — a discrete unimodal sequence with a single peak. We want to find the index of the maximum.

| Step | lo | hi | m1 = lo + (hi-lo)/3 | m2 = hi - (hi-lo)/3 | arr[m1] | arr[m2] | Action | |---|---|---|---|---|---|---|---|---| | 1 | 0 | 9 | 3 | 6 | 12 | 10 | arr[m1] > arr[m2], peak in left, hi = m2 - 1 = 5 | | 2 | 0 | 5 | 1 | 4 | 3 | 15 | arr[m1] < arr[m2], peak in right, lo = m1 + 1 = 2 | | 3 | 2 | 5 | 3 | 4 | 12 | 15 | arr[m1] < arr[m2], peak in right, lo = m1 + 1 = 4 | | 4 | 4 | 5 | 4 | 5 | 15 | 14 | arr[m1] > arr[m2], peak in left, hi = m2 - 1 = 4 | | 5 | 4 | 4 | — | — | — | — | lo == hi, return arr[4] = 15 |

Five comparisons, ten elements. For comparison, binary search on this same problem (probing slope direction at each step) would take ~⌈log₂ 10⌉ = 4 iterations of one comparison each. Ternary spent ~10 array reads to binary’s ~4. The asymptotic complexity is the same class but the constants are visibly worse.

A slightly different framing: you can in fact solve “find peak in unimodal array” with binary search by examining arr[mid] vs arr[mid + 1] to determine which side the peak is on (going up or going down); each step makes one comparison and discards half the range. This is what LC 162 expects. Ternary search would also work, with worse constants — and is not the recommended approach for that problem.

3. Pseudocode

3.1 Discrete Ternary Search (Find Peak Index)

ternary_search_discrete(arr, lo, hi):
    while lo < hi:
        m1 := lo + (hi - lo) / 3
        m2 := hi - (hi - lo) / 3
        if arr[m1] < arr[m2]:
            lo := m1 + 1                        # peak is to the right of m1
        else:
            hi := m2 - 1                        # peak is to the left of m2
    return lo                                   # lo == hi: peak found

The integer-division partition into thirds is approximately equal-thirds; for an interval of size 9 it produces probes at offsets 3 and 6; for size 10 at offsets 3 and 7. This asymmetry doesn’t affect correctness as long as m1 < m2 strictly, which holds whenever hi - lo >= 2. The base case hi - lo < 2 (interval of size 1 or 2) is handled by the loop condition lo < hi; when lo == hi we’ve narrowed to a single index and return.

3.2 Continuous Ternary Search (Find Maximum of f on [a, b])

ternary_search_continuous(f, a, b, tolerance):
    while b - a > tolerance:
        m1 := a + (b - a) / 3
        m2 := b - (b - a) / 3
        if f(m1) < f(m2):
            a := m1
        else:
            b := m2
    return (a + b) / 2

Two distinctions from the discrete version:

1. Termination condition is a numerical tolerance, not interval size 1. You can iterate until the interval is smaller than the desired precision (e.g., 1e-9).
2. Updates use m1 / m2 directly, not m1 + 1 / m2 - 1. In continuous space there’s no “next-integer” notion; the probe positions themselves are the new bracket endpoints.

The number of iterations to reduce the interval from initial size L to tolerance ε is ⌈log_{3/2}(L / ε)⌉. For L = 1 and ε = 10⁻⁹, that’s ⌈log_{3/2} 10⁹⌉ ≈ 51 iterations. Compare with binary search via gradient sign (Newton’s method or analogous): O(log L/ε) with base 2, ~30 iterations for the same precision. Ternary doesn’t need derivatives, which is its main selling point in continuous optimization.

4. Python Implementation

4.1 Discrete: Find Peak Index in a Unimodal Array

def find_peak_unimodal(arr: list[int]) -> int:
    """Return index of the maximum in a strictly unimodal array."""
    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

Correctness sketch. Loop invariant: the peak index lies in [lo, hi]. Initially trivially true. After the comparison:

• If arr[m1] < arr[m2], then by unimodality the function is still rising at m1 (otherwise the peak would be at or before m1, contradicting arr[m1] < arr[m2] since m2 > m1). So the peak is strictly to the right of m1, justifying lo = m1 + 1.
• If arr[m1] > arr[m2], by symmetry the peak is strictly to the left of m2, justifying hi = m2 - 1.
• If arr[m1] == arr[m2], in the strict-unimodality model this can’t happen; in the weak-unimodality model (plateaus allowed), the peak could be anywhere in [m1, m2], and either update is correct (we’ve chosen the right-shrinking branch).

The loop terminates because lo < hi implies m1 < m2 (since (hi - lo) // 3 >= 1 when hi - lo >= 3; the hi - lo == 1 and hi - lo == 2 cases both make m1 == lo, m2 == hi - 1 work out to make progress).

4.2 Continuous: Maximize f(x) on [a, b] Where f Is Unimodal

def maximize_unimodal(f, a: float, b: float, eps: float = 1e-9) -> float:
    """Return x* ∈ [a, b] approximately maximizing the unimodal f, within eps."""
    while b - a > eps:
        m1 = a + (b - a) / 3
        m2 = b - (b - a) / 3
        if f(m1) < f(m2):
            a = m1
        else:
            b = m2
    return (a + b) / 2

Use case: maximizing a continuous unimodal function whose closed-form derivative is unavailable or expensive. Examples include Bayesian posterior modes when the gradient is intractable, parameter tuning of a noiseless simulator, or finding the apex of a parabolic trajectory given only an evaluation oracle.

5. Complexity

Time: O(log_{3/2} n) ≈ 1.71 × log₂ n in the discrete case; same class as binary search but with a base of 3/2 instead of 2. Each step reduces the interval to 2/3 of its previous size (you keep two of three thirds), so after k steps the interval is (2/3)^k × n; setting this to 1 gives k = log_{3/2} n.

In function evaluations, the cost is 2 × log_{3/2} n ≈ 3.42 × log₂ n because each iteration evaluates f at two probe points. Compare with binary search’s 1 × log₂ n evaluations per element discarded. Net: ternary search performs roughly 3.42× more function evaluations than binary search to achieve the same precision on a problem amenable to both.

Space: O(1) iterative; O(log n) recursive (recursion stack).

Why not a k-ary search for k > 3? You might guess that 4-ary search (“partition into four, discard one or two”) would do better; it doesn’t. The math: a k-ary search uses k - 1 probes per step to identify which of k parts contains the answer (under the analogous predicate), discarding 1 / k of the range. Comparisons per bit of progress: (k - 1) / log₂ k. For k = 2 this is 1 / 1 = 1. For k = 3: 2 / log₂ 3 ≈ 1.26. For k = 4: 3 / 2 = 1.5. The minimum is at k = e ≈ 2.718, with k = 3 and k = 2 both close to optimum but k = 2 slightly better. Binary search is information-theoretically optimal among k-ary searches for monotone predicates; ternary is suboptimal. This is the formal version of “binary halves; ternary thirds.”

For unimodal search the analysis differs slightly because each probe is an f evaluation rather than a yes/no comparison, but the conclusion stands: binary search via gradient-sign or via paired-probe (f(mid) vs f(mid + 1)) outperforms ternary on every measurable axis when applicable.

6. Why Binary Search Beats Ternary on Sorted Arrays

The folk question “should I use ternary search instead of binary search?” almost always has the answer “no” when the input is a sorted array. The reasoning:

1. A sorted array is a monotone predicate, and binary search is optimal on monotone predicates (matches the information-theoretic lower bound of ⌈log₂ n⌉ comparisons in the worst case).
2. Ternary search uses 2 comparisons per iteration to discard 1/3 of the range. Binary uses 1 comparison to discard 1/2. Per comparison, binary discards log₂ 2 = 1 bit of information; ternary discards (1/2) × log₂(3/2) ≈ 0.29 bits per comparison. Binary is 3.4× more comparison-efficient.
3. There is no setting in which ternary search dominates binary on sorted-array search — the “ternary on monotone” use case has no advantage over binary, and the constant factors are strictly worse.

The only reason to use ternary is when the predicate is unimodal but not monotone, and you don’t have a way to convert unimodality into a monotone predicate. For LC 162 (Find Peak Element) you can convert: arr[mid] < arr[mid + 1] is a monotone predicate (false on the descending side of the peak, true on the ascending side). So binary search applies and is preferred. Pure unimodality without an exploitable monotone derivative is mostly a continuous-optimization story.

7. When Ternary Search Is the Right Choice

The narrow but legitimate use cases:

7.1 Continuous Unimodal Optimization Without a Derivative

Maximize f(x) on [a, b] where f is unimodal and you don’t have f'. Ternary search converges in O(log_{3/2}(L/ε)) evaluations. Examples: tuning a hyperparameter when you only have a black-box f, finding the apex of a parabolic interpolation, optimizing a simulator output. In these settings ternary search competes against Golden-Section Search, which uses the golden ratio φ ≈ 1.618 to reuse one probe per iteration, halving the per-step cost while keeping the same (1/φ)^k interval shrinkage. Golden-section search beats ternary in continuous settings with the same robustness; the only reasons to prefer ternary are pedagogical simplicity and not needing the irrational ratio.

7.2 Discrete Unimodal Functions Where You Can’t Compare Slopes

If arr[i] and arr[i+1] aren’t both available — say, you can sample arr[i] cheaply but arr[i+1] requires a separate expensive computation — ternary search trades two arbitrary samples for two adjacent ones. This is unusual; in most discrete settings the binary “compare adjacent” trick works.

7.3 Noisy Functions Where Slope Sign Is Unreliable

If your function has noise (Monte-Carlo simulation output, empirical measurement), the slope sign at a single point is unreliable; ternary search’s two-probe-at-spread-positions approach is more noise-robust because the two probes are far apart ((b-a)/3) and small noise won’t flip the comparison. This is more often a setting for Stochastic Approximation or Bayesian Optimization, but ternary can work as a simple baseline.

7.4 Pedagogical Context

Ternary search appears in algorithms textbooks largely as a contrast to binary search — to make the point that the choice of k in k-ary search matters and that binary search’s optimality has an information-theoretic explanation. It’s worth knowing for that reason alone.

8. Variants and Related Techniques

8.1 Golden-Section Search

Replace the equal-thirds split with a split at the golden ratio. Two probes at a + (1 - 1/φ)(b - a) and a + (1/φ)(b - a), where φ = (1 + √5) / 2 ≈ 1.618. The clever bit: after each step, one of the two probes lies at a golden-ratio position within the new shorter interval, so it can be reused — only one new probe per iteration. This halves the function-evaluation count to ~log_φ n ≈ 1.44 × log₂ n evaluations, beating ternary search in any setting where evaluations are expensive. Golden-section search is the correct choice for continuous unimodal optimization without derivatives; ternary search is a simpler-to-explain alternative with no real advantages.

8.2 Fibonacci Search

A precursor of golden-section search using Fibonacci numbers to determine probe positions. Useful in pre-floating-point computing where Fibonacci ratios approximate the golden ratio without irrational arithmetic. Mostly historical interest; same O(log n) complexity.

8.3 Brent’s Method

Combines golden-section search with parabolic interpolation: when the function looks locally parabolic (most smooth functions are), fit a parabola through the three current probes and jump to its vertex; fall back to golden-section when the parabolic step would be wild. Standard tool in scientific computing libraries (scipy.optimize.brentq for root-finding, scipy.optimize.minimize_scalar(method='brent') for minimization). Strictly better than pure ternary or golden-section on smooth functions.

8.4 Trinary / Quaternary Search Tries

Unrelated despite the name: trinary search trees (“ternary search tries”) store strings using 3-way branching at each node by comparing characters with <, ==, >. This is a data structure for string lookup, not a search algorithm in the same sense as ternary search.

9. Pitfalls

9.1 Applying It to Non-Unimodal Functions

The single biggest correctness trap. Ternary search on a function with two peaks returns one of them (whichever the probes happen to pick), silently discarding the other. There is no way to detect this from the algorithm’s output — the result looks fine. Always verify the unimodality precondition before deploying ternary search, the same way you verify sortedness before deploying binary search.

9.2 Reaching for Ternary on Sorted Arrays

LeetCode candidates sometimes “innovate” by using ternary search on problems amenable to binary search, citing intuition like “more probes per step must be better.” The constants are strictly worse; binary search is information-theoretically optimal on monotone predicates. Use binary unless you genuinely have a unimodal-but-not-monotone problem.

9.3 Off-by-One on Discrete Updates

The discrete lo = m1 + 1 (not lo = m1) and hi = m2 - 1 (not hi = m2) updates rely on the fact that the comparison arr[m1] < arr[m2] rules out m1 itself as the peak (because arr[m1] < arr[m2] and m2 is also a candidate, so even if the peak is at m1 the value would equal something later, contradicting the strict unimodality). For weakly unimodal arrays (plateaus allowed), the strict update is incorrect — use lo = m1 and hi = m2. Match the convention to the unimodality kind.

9.4 Numerical Tolerance Issues in Continuous Variant

Setting eps too small (1e-15) can cause the loop to never terminate in floating-point because m1 and m2 round to identical values. Standard practice: pick eps no smaller than 1e3 times machine epsilon (~2.2e-13 for float64), and always include a maximum-iteration safety cap.

9.5 Equal Function Values at the Two Probes

In the discrete case with strict unimodality this is impossible; in the continuous case it’s measure-zero (so essentially never happens) but in degenerate flat regions it can occur. The “ties go right” choice in the pseudocode (if arr[m1] < arr[m2], the equality branch goes to the else side that shrinks hi) is one valid resolution; the other is if arr[m1] <= arr[m2], which shrinks differently. Either is correct as long as you’re consistent and the input genuinely satisfies unimodality.

9.6 Confusing Ternary Search with Ternary-Tree Search

“Ternary search tree” is an unrelated data structure (a 3-ary trie variant for string keys). They share no algorithmic content. Don’t conflate.

10. Diagram — How Ternary Search Shrinks an Interval

flowchart TD
    subgraph initial ["Initial interval"]
        S0["[lo .................. hi]<br/>length = L"]
    end
    subgraph step ["One ternary step"]
        S1["[lo === m1 === m2 === hi]<br/>two probes split into thirds"]
        S2A["arr[m1] < arr[m2] → discard left third<br/>new = [m1+1 .. hi], length ≈ 2L/3"]
        S2B["arr[m1] > arr[m2] → discard right third<br/>new = [lo .. m2-1], length ≈ 2L/3"]
        S1 --> S2A
        S1 --> S2B
    end
    S0 --> S1

What this diagram shows. Each iteration of ternary search reduces the candidate interval by a factor of 2/3 — you discard exactly one of the two outer thirds based on the comparison of f(m1) and f(m2), and keep the other outer third plus the middle third. The middle third is preserved because the peak (or valley) could be anywhere in it; only by examining one of the outer thirds and seeing the function rising or falling can you confidently rule that third out. Compare this picture with the analogous diagram for binary search (which discards exactly one half per step using one comparison); ternary discards a third per step using two comparisons. The arithmetic of “comparisons per bit of range eliminated” is what makes binary search information-theoretically optimal among k-ary searches: binary is 1 comparison per 1 bit (log₂ 2); ternary is 2 comparisons per log₂(3/2) ≈ 0.585 bits, or ~3.42 comparisons per bit. Binary’s efficiency is roughly 3.42× better in this metric.

11. Common Interview Problems

#	Problem	Why mention ternary
LC 162	Find Peak Element	Solvable by ternary; binary via slope-sign is preferred
LC 852	Peak Index in a Mountain Array	Same — binary preferred
LC 1095	Find in Mountain Array	Two-stage: find peak (binary), then binary-search each side
(Codeforces)	Maximize a parabola on integers	Ternary (or close-form quadratic if solvable)
(numerical)	Find argmax of an empirical noisy unimodal f(x)	Golden-section search (ternary’s better cousin)
(graphics)	Find the highest point on a Bezier curve	Continuous ternary or Brent’s method
(DP optimization)	Convex/concave 1D DP optimization (Knuth’s optimization, divide-and-conquer DP)	Sometimes ternary search inside an outer DP

The conspicuous absence of “this is the problem for ternary search” in standard interview prep is the message: ternary search is rarely the right algorithm, and recognizing that is part of using it correctly. The questions that genuinely demand ternary tend to be in numerical optimization or competitive programming with carefully constructed unimodal-but-not-monotone payoffs, not in standard SWE interviews.

12. Open Questions

• Does k-ary search ever win in practice for k > 2? Possibly on cache-sensitive workloads where probing 3-4 close indices is cheaper than 2 distant ones.

  Uncertain k-ary search (k > 2) beats binary search on real hardware for in-memory comparison search. Reason: the comparison-count model says no (binary is information-theoretically optimal among k-ary searches on monotone predicates — see §5), but that model ignores cache-line and prefetch effects, and I have not found a primary benchmark settling the in-memory case either way. To resolve: a controlled microbenchmark of k-ary vs binary search across cache hierarchies, or a citation to one. Note that B+-trees deliberately use very high fanouts (k = 100+) for an I/O-bound reason (one node read per disk/page access), which is a different cost model from in-memory comparison count and does not directly answer the question. uncertain

  Verify: whether

• Is there a closed-form characterization of the exact class of functions where ternary strictly beats binary? Conjecturally: only functions where unimodality is the strongest exploitable structural property and no monotone-derivative trick applies — a narrow class that mostly lives in continuous optimization.
• How does ternary interact with Binary Search on Answer? In principle if the answer-space is unimodal in some figure-of-merit (rare), ternary could replace binary in the outer loop. I’m not aware of a canonical interview problem that requires this.

13. See Also

• Binary Search — the more efficient alternative for monotone predicates; the default tool
• Exponential Search — for unbounded sorted sequences
• Interpolation Search — for sorted arrays with known value distribution
• Linear Search — the brute-force baseline
• Big-O Notation — for the log_{3/2} vs log_2 analysis
• Convex Hull Trick — related continuous-optimization technique that exploits problem structure rather than search
• SWE Interview Preparation MOC