SearchingSearching

Ternary Search

Find the extremum of a unimodal function by discarding one third of the range per step.

Learn Ternary Search →
2
0
↑lo
5
1
8
2
12
3
16
4
23
5
38
6
56
7
72
8
91
9
↑hi
1/5Search for 23 in the sorted range [0, 9]. Ternary search probes two points per iteration and keeps one of three thirds.
Being compared with targetTarget foundEliminated
PseudocodeLearn Ternary Search →
1lo = 0, hi = n - 1
2while lo <= hi:
3  m1 = lo + (hi - lo) // 3; m2 = hi - (hi - lo) // 3
4  if a[m1] == target: return m1
5  if a[m2] == target: return m2
6  if target < a[m1]: hi = m1 - 1
7  elif target > a[m2]: lo = m2 + 1
8  else: lo = m1 + 1, hi = m2 - 1
9return -1
Variables
lo0
hi9
target23
Complexity
best O(log n)
avg O(log n)
worst O(log n)
space O(1)
Speed