Ternary search
Splitting search into thirds, why it is O(log n), and why binary still usually wins. · 7 min read
If binary search asks one middle question, ternary search asks two. Pick two probes, m1 and m2, so the sorted window is split into three parts. If the target is smaller than a[m1], keep the left third; if larger than a[m2], keep the right third; otherwise keep the middle third.
def ternary_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
third = (hi - lo) // 3
m1, m2 = lo + third, hi - third
if a[m1] == target: return m1
if a[m2] == target: return m2
if target < a[m1]: hi = m1 - 1
elif target > a[m2]: lo = m2 + 1
else: lo, hi = m1 + 1, m2 - 1
return -1Interactive visualization: Shrinking the search window by thirds — step through it frame by frame on this page.
Bases in search
Binary search leaves 1/2 of the candidates each round. Ternary search leaves 1/3. More generally, a b-way search that keeps one of b equal regions takes about log_b n rounds.
start with n candidates— The whole sorted array is still possible.n → n/3 → n/9 → … → 1— Each ternary round keeps one third.after k rounds: n / 3ᵏ = 1— Stop when the window has one candidate.3ᵏ = n ⟹ k = log₃ n— The base is 3 because each step splits into thirds.
Result: O(log n)