How Ternary Search Works
Ternary search splits the range into thirds instead of halves. It sounds faster and is measurably slower, which makes it the clearest lesson in reading complexity honestly.
- Ruled out
- Still possible
- Checked now
- Found
Step 1 of 6
Looking for 158 in 16 sorted values, from 4 to 196.
Counters
- Steps
- 0
- Result
- -
- Still possible
- 16
- of 16
- Worst case
- 6
- steps for this size
Settings
Two to 64 numbers. Sorted ascending before the search runs.
Ternary search
- 1
lo = 0; hi = n-1 - 2
while lo <= hi: - 3
m1 = lo + (hi - lo) / 3 - 4
m2 = hi - (hi - lo) / 3 - 5
if a[m1] == target: return m1 - 6
if a[m2] == target: return m2 - 7
if target < a[m1]: hi = m1 - 1 - 8
elif target > a[m2]: lo = m2 + 1 - 9
else: lo = m1 + 1; hi = m2 - 1
The same array, every algorithm
Probes on the values above, cheapest first. One probe is one value actually looked at.
- Interpolation1
- Ternary3
- Binary4
- Jump5
- Exponential8
- Linear13
How the six compare
| Algorithm | Best | Average | Worst | Needs a sorted array |
|---|---|---|---|---|
| Linear | O(1) | O(n) | O(n) | No |
| Binary | O(1) | O(log n) | O(log n) | Yes |
| Ternary | O(1) | O(log n) | O(log n) | Yes |
| Jump | O(1) | O(√n) | O(√n) | Yes |
| Exponential | O(1) | O(log n) | O(log n) | Yes |
| Interpolation | O(1) | O(log log n)* | O(n) | Yes |
Interpolation search only reaches that average when the gaps between the values are even.
Complexity
| Best | Average | Worst | Extra memory |
|---|---|---|---|
| O(1) | O(log₃ n) | O(log₃ n) | O(1) |
log₃ n looks better than log₂ n until you count comparisons: 2·log₃ n ≈ 1.26·log₂ n. Fewer rounds, more work per round, slower overall.
How ternary search works
Ternary search picks two split points and narrows the range to one of three parts, using up to two comparisons per round. Because each round eliminates two thirds instead of one half, it needs fewer rounds than binary search — and because each round costs two comparisons instead of one, it does about 26% more comparisons in total. It is the standard demonstration that a smaller log base is not automatically a win.
- Compute two split points, one third and two thirds along the range.
- Compare the target with the element at the first split; if it is smaller, keep the first third.
- Otherwise compare with the second split; smaller keeps the middle third, larger keeps the last third.
- Repeat on the surviving third until the range is empty or a split matches.
Implementation
The same algorithm the visualiser is running, written to be read.
def ternary_search(values, target):
low, high = 0, len(values) - 1
while low <= high:
third = (high - low) // 3 or 1
first, second = low + third, high - third
if values[first] == target:
return first
if values[second] == target:
return second
# Two comparisons to discard two thirds - that is the trade.
if target < values[first]:
high = first - 1
elif target > values[second]:
low = second + 1
else:
low, high = first + 1, second - 1
return -1When to use it
- Use it to find the extremum of a unimodal function, which is what ternary search is genuinely for — there the two probes tell you which side the peak is on, and binary search cannot answer that at all.
- Use it as a teaching example of comparing algorithms by total operations rather than by asymptotic shape.
- Avoid it for searching sorted arrays. Binary search does strictly less work.
Check yourself
If the animation made sense, these should too.
Splitting into thirds needs fewer rounds than halving. Why is it still slower?
Because each round costs two comparisons instead of one. The number of rounds falls to log₃ n, but the total comparisons are 2·log₃ n ≈ 1.26·log₂ n - about 26% more work than binary search on the same array.
What is ternary search genuinely good for?
Finding the extremum of a unimodal function. Two probes tell you which side of the peak you are on, which a single midpoint comparison cannot; there it is the right tool, and searching sorted arrays is not.