How Ternary Search Works
index 016 of 16 still possible15
- Ruled out
- Still possible
- Checked now
- Found
1/6
Looking for 158 in 16 sorted values, from 4 to 196.
Settings
More options
Is it in the array?
Gaps between values
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
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.