Wyszukiwanie interpolacyjne

Mamy daną posortowaną N-elementową tablicę zawierającą losowe liczby. Chcemy sprawdzić czy znajduje się wśród nich liczba k. Niejeden programista w tym miejscu krzyknie: "Wyszukiwanie binarne!". Pytanie: Czy można szybciej? Można!

Przypomnijmy może szybko implementację wyszukiwania binarnego:

int bsearch(int* A, int N, int k)
{
  int l = 0, r = N-1;

  while (l <= r)
  {
    int m = (l + r) / 2;

    if (A[m] == k) return m;
    else if(A[m] < k) l = m + 1;
    else r = m - 1;
  }

  return -1;
}

W poszukiwaniu interpolacyjnym korzystamy z następującego spostrzeżenia. Gdy przeszukujemy książkę telefoniczną szukając pana Wołodyjowskiego, to zazwyczaj nie otwieramy książki na stronie środkowej (jak to robi wyszukiwanie binarne) lecz na jej końcu. Z kolei gdy szukamy w książce pani Adamskiej to zaglądamy na początek książki. Aby zaimplementować ten algorytm, wystarczy w algorytmie wyszukiwania binarnego zamienić linijkę:

int m = (l + r) / 2;

na następującą:

int m = l + (k - A[l]) * (r - l) / (A[r] - A[l]);

Zaletą takiego rozwiązania jest złożoność. Algorytm dla tablicy wypełnionej losowymi wartościami używa mniej niż lg lg N + 1 porównań (dla przypomnienia - wyszukiwanie binarne wykonuje lg N + 1 porównań). Funkcja ta rośnie bardzo wolno. Dla przykładu lg lg 10³⁰⁸ < 10. A w przypadku, gdy tablica jest jeszcze regularniej ułożona niż w sposób losowy to liczba wymaganych porównań jest jeszcze mniejsza!

Wadą takiego rozwiązania jest koszt obliczenia wartości m (wykonujemy tutaj dużo operacji arytmetycznych) co dla nie wielkich wartości N może spowodować, że algorytm wyszukiwania binarnego będzie działał szybciej.

Ponadto algorytm nie nadaje się do wyszukiwania w tablicach, o których nie wiemy czy elementy w niej zawarte są równomiernie rozłożone. Algorytm dla przypadków pesymistycznych może wymagać nawet czasu liniowego.