Ternary search

O(log₃ n)

Ternary search works like binary search but divides the range into three parts using two probe points (at the ⅓ and ⅔ marks). Each step it can discard two of the three parts, so it's O(log₃ n) comparisons — slightly more comparisons than binary search in practice, but the same logarithmic class. The array must be sorted.

Array
Edit the input and press Play

How it works

  1. Probe at the ⅓ and ⅔ points of the current range.
  2. If either equals the target, you're done.
  3. If the target is below the first probe, keep the left third.
  4. If above the second probe, keep the right third; otherwise keep the middle.

Pseudocode

1ternarySearch(a, target):           # O(log₃ n) — a is sorted2  lo ← 0; hi ← n-13  while lo ≤ hi:4    m1 ← lo + (hi-lo)/3; m2 ← hi - (hi-lo)/35    if a[m1] = target: return m16    if a[m2] = target: return m27    if target < a[m1]: hi ← m1-18    else if target > a[m2]: lo ← m2+19    else: lo ← m1+1; hi ← m2-110  return -1