Interpolační vyhledávání je vyhledávací algoritmus pro nalezení zadané hodnoty v uspořádaném seznamu hodnot. Algoritmus je vylepšením binárního vyhledávání pro případy, kdy jsou hodnoty v seznamu nejen seřazené, ale zároveň rovnoměrně rozložené. Tuto metodu intuitivně používají lidé například při vyhledávání ve slovníku – odhadnou, kde by přibližně mohlo hledané heslo být (např. heslo začínající písmenem „K“ bude pravděpodobně někde před polovinou slovníku) a otevřou slovník na odhadnutém místě. Podle odchylky postupují dopředu nebo dozadu o menší nebo větší počet stránek.
Interpolační vyhledávání se zakládá na myšlence, že u rovnoměrně rozložených hodnot v seznamu můžeme odhadnout umístění a tím snížit počet nutných kroků k nalezení prvku. Jako příklad budeme uvažovat seznam čísel 1, 2, 3 … až 1000. Pokusíme se najít prvek 125. Pokud bychom hledali pomoci binárního vyhledávání, prvním testovaným prvkem by bylo číslo 500, poté číslo 250 a nakonec námi hledané číslo 125. Interpolační vyhledávací algoritmus odhadne pozici a přímo přejde na prvek 125.
Složitost tohoto algoritmu pro rovnoměrně rozložená data je O(log log n). V nejhorším případě ovšem může být složitost až O(n). Aby se zabránilo nejhoršímu případu, je možné kombinovat interpolační vyhledávání s binárním vyhledáváním – například střídat vždy jeden krok interpolačního vyhledávání a jeden binárního vyhledávání.
Implementace Ukázka implementace v jazyce C++. template <typename T> int interpolation_search(T arr[], int size, T key) { int low = 0; int high = size - 1 ; int mid ;
while (arr[high] != arr[low] && key >= arr[low] && key <= arr[high]) { mid = low + (key - arr[low]) * ((high - low) / ( arr[high] - arr[low])) ;
if (arr[mid] < key) low = mid + 1 ; else if (key < arr[mid]) high = mid - 1; else return mid;
if (key == arr[low]) return low ; else return -1; }
Související články Binární vyhledávání
Kategorie:Vyhledávací algoritmy