Ternary search

O(log₃ n)

Ternary search funguje jako binární, ale dělí rozsah na tři části dvěma sondami (v ⅓ a ⅔). V každém kroku může zahodit dvě ze tří částí, takže je O(log₃ n) porovnání — v praxi o něco víc porovnání než binární, ale stejná logaritmická třída. Pole musí být seřazené.

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Zkus body v ⅓ a ⅔ aktuálního rozsahu.
  2. Když se některý rovná hledané hodnotě, hotovo.
  3. Když je hledaná hodnota pod první sondou, ponech levou třetinu.
  4. Když nad druhou sondou, ponech pravou třetinu; jinak prostřední.

Pseudokód

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