Overview
Ternary Search cuts the range into thirds instead of halves. Each round places two probes inside the interval, compares them, and discards the third that cannot contain the answer.
On a sorted array it is a curiosity rather than an improvement: it removes a third of the range per round but pays two comparisons to do it, where binary search removes half for one. Its real home is optimisation — finding the peak of a unimodal function, where you cannot ask 'is the target bigger or smaller' because there is no target, only a shape.
How Ternary Search works
- Take the current interval [lo, hi] and compute two split points: m1 one third of the way in, m2 two thirds of the way in.
- Compare the target with the value at m1. If it matches, stop; if it is smaller, the answer lies in [lo, m1 − 1].
- Otherwise compare with the value at m2. If it matches, stop; if it is larger, the answer lies in [m2 + 1, hi].
- If it falls between the two probes, the answer lies in the middle third [m1 + 1, m2 − 1].
- Repeat on the surviving third until it matches or the interval is empty.
When to use it
- Finding the maximum or minimum of a unimodal function — the case where it genuinely beats the alternatives.
- Optimisation problems in competitive programming where the search space is continuous and the objective has a single peak.
- Teaching the divide-and-conquer idea: it makes visible that the split ratio is a tunable choice, not a law.
- Not the tool for plain lookup in a sorted array — binary search does the same job with fewer comparisons.
Complexity analysis
Each round shrinks the range to a third, so the number of rounds is log₃ n — fewer than binary search's log₂ n. But each round costs up to two comparisons instead of one, and 2·log₃ n is about 1.26·log₂ n. So it does strictly more comparison work despite touching fewer rounds, which is why binary search stays the default. Space is O(1) iteratively.
Frequently asked questions
If it examines fewer rounds, why is it slower?
Because rounds are not the cost — comparisons are. Ternary search buys a smaller round count by spending two comparisons per round, and the arithmetic works out against it: roughly 1.26 times the comparisons of binary search for the same array.
What is a unimodal function, and why does it matter here?
One that rises to a single peak then falls (or the mirror image). That shape is what lets two probes decide which side the peak is on: if f(m1) < f(m2) the peak cannot be left of m1. With two peaks that inference breaks and the search can discard the region containing the answer.
Could you split into four parts, or ten?
You can, and it gets worse each time. k-ary search needs k − 1 comparisons to remove a (k−1)/k fraction, and that ratio degrades as k grows. Two is the optimum for comparison-based search, which is the deeper reason binary search is everywhere.