Back to Study Material Data Structures and Algorithms

Ternary Search

Ternary search is an algorithm designed to find the maximum or minimum of a unimodal function, meaning a function that rises to a single peak and then fall...

Ternary Search

Searching a Unimodal Function

Ternary search is an algorithm designed to find the maximum or minimum of a unimodal function, meaning a function that rises to a single peak and then falls, or falls to a single trough and then rises. Unlike binary search, which eliminates half the search space per step by comparing to a fixed target, ternary search eliminates one third of the space per step by comparing function values at two interior points.

To find the maximum of a unimodal function over the interval from L to R, compute two points: m1 at L plus (R minus L) divided by 3, and m2 at R minus (R minus L) divided by 3. Evaluate the function at m1 and m2. If the function value at m1 is less than the value at m2, the maximum cannot be in the left third, so set L to m1. Otherwise the maximum cannot be in the right third, so set R to m2. Repeat until the interval is small enough.

A worked example: finding the minimum of the function f(x) equals x squared minus 4x plus 5 over the interval from 0 to 10. The true minimum is at x equals 2. Ternary search converges to x equals 2 within about 50 iterations when the tolerance is set to one millionth.

Time complexity is O(log base 1.5 of (range divided by tolerance)) for continuous functions, which simplifies to O(log n) where n represents the number of discrete points or the precision required. Each iteration reduces the search space by a factor of two thirds rather than one half, so ternary search requires roughly 1.7 times more iterations than binary search would on a comparable problem. Space complexity is O(1) for the iterative version.

Interview tip: if asked when ternary search is preferable to binary search, note that binary search finds a specific value in a sorted sequence, while ternary search finds an extremum of a unimodal function. The two algorithms address fundamentally different problem types despite their structural similarity.

Discrete vs Continuous Ternary Search

Ternary search has two distinct forms depending on whether the input domain is continuous, such as a real-valued function, or discrete, such as an array of integers that forms a unimodal sequence.

In the continuous case, the algorithm runs until the interval length falls below a chosen epsilon. Because floating-point arithmetic introduces rounding errors, it is common to run a fixed number of iterations, typically 200, rather than checking the interval length. Two hundred iterations reduce the initial interval by a factor of (2/3) to the power of 200, which is astronomically small.

In the discrete case, ternary search operates on an array of integers. The midpoints m1 and m2 are integer indices. The loop continues while L is less than R. Because the interval shrinks by at least one index per step, the algorithm terminates in O(log n) steps. A subtle but important point is that when m1 equals m2 due to rounding, you must handle the comparison carefully to avoid an infinite loop. A common fix is to set m2 to m1 plus 1 in that case.

A worked example on a discrete array: the sequence 1, 3, 7, 12, 9, 5, 2 is unimodal with a peak at index 3 holding value 12. Ternary search on this array of length 7 finds the peak in at most 4 comparisons.

One practical application is optimizing a cost function in machine learning when the function is known to be convex in one dimension. Ternary search on that dimension finds the optimal hyperparameter value without exhaustive grid search.

Time complexity is O(log n) in both the continuous and discrete cases. Space complexity is O(1) for iterative implementations. The recursive form uses O(log n) stack space.

Interview tip: mention that for discrete unimodal arrays, golden-section search is sometimes preferred because it reuses one of the two function evaluations from the previous step, reducing total evaluations by about 38 percent compared to naive ternary search.

Comparing Ternary and Binary Search

A common question in interviews and competitive programming discussions is whether ternary search is faster than binary search. The answer requires careful thought because the two algorithms solve different problems and comparing them directly is only meaningful when both are applicable.

When both can be applied, for instance on a sorted unimodal array where you want to find the peak, binary search is actually faster. Here is why. Binary search eliminates half the search space with one comparison. Ternary search eliminates one third of the space but requires two comparisons to do so. The number of comparisons binary search needs is log base 2 of n. The number ternary search needs is 2 times log base 1.5 of n. Evaluating these: log base 1.5 of n equals log base 2 of n divided by log base 2 of 1.5, which is approximately log base 2 of n divided by 0.585. Multiplied by 2, this gives roughly 3.42 times log base 2 of n. Binary search uses fewer comparisons.

However, ternary search remains the correct choice when the function cannot be expressed as a simple array lookup and each evaluation is expensive, such as a simulation that takes minutes to run. In that case, the number of function evaluations matters more than the number of comparisons, and ternary search and binary search perform similarly in evaluations per iteration.

A worked example: estimating the optimal launch angle for a projectile to maximize range, where computing the range at a given angle requires a physics simulation. Ternary search finds the best angle with about 50 simulation calls, which is practical. Trying all angles in one-degree increments would require 90 calls with less precision.

Time complexity in terms of function evaluations: O(log base 1.5 of (range divided by tolerance)). Space complexity O(1).

Interview tip: when an interviewer asks about ternary search, show that you understand the trade-off between number of comparisons and number of function evaluations. This demonstrates depth of understanding beyond memorizing the algorithm.