18 września 2008

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 10308 < 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.

2 komentarze:

Mitrandir77 pisze...

Fajne :) Szkoda, że nie ma zastosowania na konkursach gdzie testy są układane wybitnie nielosowo.

npb pisze...

To może mieć zastosowanie na konkursach. Na przykład w sytuacji w której wyszukujemy z tablicy, którą sami utworzyliśmy (to znaczy nie została ona wczytana np. ze standardowego wejścia) i wiemy, że liczby w niej są równomiernie ułożone.