Ternary Search
Splits the search range into three thirds and compares at the two split points.
- Comparisons 0
- Result still searching
- compare
- swap
- sorted
Pseudocode
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 else if target > a[m2]: lo = m2 + 1
9 else: lo = m1 + 1; hi = m2 - 1
10 return -1
Step log
- 1Ternary search for 74 in the sorted array
How it works, runtime and memory
Ternary search is a direct generalisation of binary search that splits the current range into three parts instead of two. With m1 = lo + ⌊(hi − lo) / 3⌋ and m2 = hi − ⌊(hi − lo) / 3⌋ it compares two points per iteration. If the target lies to the left of a[m1] it continues in the left third; right of a[m2] in the right third; otherwise in the middle third between m1 and m2. Runtime is O(log₃ n), asymptotically equivalent to binary search. But ternary search makes two comparisons per iteration instead of one, so it is slower in practice and rarely used as a pure search. Its main use is as an optimisation tool for unimodal (strictly increasing then decreasing) functions.
Complexity
- Best case
- O(1)
- Average case
- O(log n)
- Worst case
- O(log n)
- Extra space
- O(1)
When to use it
Classic application: finding the maximum of a unimodal function, one that rises and then falls. Examples include the peak of a parabola or the optimal throw range of a projectile. As a pure array search, inferior to binary search.