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
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
More options
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 |
Scroll the table sideways for the rest of the columns.
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) |
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. Because each round costs two comparisons instead of one, it ends up doing about 26% more comparisons in total. A smaller log base is not automatically a win.
Implementation
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.