Interpolation search

O(log log n) avg

Interpolation search vylepšuje binární vyhledávání pro rovnoměrně rozložená seřazená data: místo prostředku odhaduje pozici úměrně tomu, kam hledaná hodnota spadá mezi krajní hodnoty lo a hi. Na rovnoměrných datech může dosáhnout O(log log n); na zkosených se zhorší k O(n).

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Odhadni pozici sondy interpolací hledané hodnoty mezi nejmenší a největší hodnotou rozsahu.
  2. Porovnej hodnotu tam s hledanou.
  3. Když je menší, hledej v pravé části; když větší, v levé.
  4. Opakuj, dokud nenajdeš nebo rozsah hledanou hodnotu už neobklopuje.

Pseudokód

1interpolationSearch(a, target):     # O(log log n) avg — a is sorted2  lo ← 0; hi ← n-13  while lo ≤ hi and a[lo] ≤ target ≤ a[hi]:4    pos ← lo + (target-a[lo])*(hi-lo) / (a[hi]-a[lo])5    if a[pos] = target: return pos6    if a[pos] < target: lo ← pos+17    else: hi ← pos-18  return -1