AlgoThrive
← All searching algorithms

Ternary Search

CheckingRuled outFound

array

target = 12
2
4
6
9
12
15
18
20
0lo
1
2
3
4
5
6
7hi

pseudocode

ternarySearch(a, target, lo, hi)
  while lo <= hi
    mid1 = lo + (hi - lo) / 3
    mid2 = hi - (hi - lo) / 3
    if a[mid1] == target return mid1
    if a[mid2] == target return mid2
    if target < a[mid1] hi = mid1 - 1
    else if target > a[mid2] lo = mid2 + 1
    else lo = mid1 + 1; hi = mid2 - 1
  return -1

Frame 1 / 5

Searching range [0…7] using two midpoints

divide range into 3 equal parts

4

Pick a value that is in the array — or one that isn't, to watch the search fail.

3–16 integers between 1 and 20 — the array is sorted for you, because binary search needs ordered data.