Interpolační vyhledávání

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