Ternary Search
Splits the range into three parts with two probes per step. Fewer iterations than binary search but more comparisons each — also finds extrema of unimodal functions.
- Category
- Searching
- Time complexity
- O(log₃ n) (Base-3 log is the same complexity class as O(log n) — the base only changes a constant factor. Written this way to show it takes more comparisons per step than binary search, not because it grows differently.)
- Space complexity
- O(1)
Pseudocode
m1 ← lo + (hi−lo)/3 m2 ← hi − (hi−lo)/3 compare t to a[m1], a[m2] keep the correct third
Reference implementation
m1 = lo + (hi - lo) // 3
m2 = hi - (hi - lo) // 3
if t < a[m1]: hi = m1 - 1
elif t > a[m2]: lo = m2 + 1
else: lo, hi = m1 + 1, m2 - 1