Wyszukiwanie Interpolacyjne

Algorytm

Wyszukiwanie Interpolacyjne to poprawiona wersja Wyszukiwania Binarnego, które wymagało posortowanej tablicy. W tym szczególnym przypadku tablic wyszukiwanie wykorzystuje fakt, że jeśli szukany element jest większy od pewnego elementu e na liście to wszystkie wartości przed elementem e też są mniejsze od szukanej wartości. Jak wiadomo tego typu rozwiązanie pozwoliło na uzyskanie bardzo szybkiego algorytmu o złożoności czasowej O(log n), gdzie n to liczba elementów na liście.

Wśród posortowanych tablic można znaleźć takie, które mają rozkład wartości liniowy, albo bardzo zbliżony do liniowego. Tablicą z rozkładem liniowym jest np. {1, 2, 3, 4, 5} (liniowy) czy {1, 2, 4, 5, 6} (prawie liniowy), ale już {1, 2, 100, 101} nie można zaliczyć do rozkładu liniowego. Przypatrując się tablicom można zauważyć, że w niektórych przypadkach środek wyszukiwania można nieco przesunąć w lewo, albo prawo. Właśnie tę własność wykorzystuje Wyszukiwanie Interpolacyjne - "środkowym" elementem nie musi być środek pomiędzy lewym i prawym zakresem.

Pozycję p porównywanego elementu wylicza się ze wzoru:

We wzorze x - szukana wartość, a - indeks zakresu dolnego, a b - indeks zakresu górnego, tab[k] - k-ty element przeszukiwanej tablicy. W ten sposób do szukanego elementu w tablicy z rozkładem liniowym przesuwamy się znacznie szybciej niż w Wyszukiwaniu Binarnym. Zasada zawężania przedziału przeszukiwanego jest taka sama jak we wspomnianym wyszkuwianiu.

Wyszukiwanie polega, aby na bieżąco przechowywać a - indeks ograniczenia dolnego oraz b - indeks ograniczenia górnego. Dopóki a ≤ b należy wyliczać wartość pozycji p. Jeśli na wyliczonej pozycji znajduje się element to zwracamy pozycję p. W przeciwnym wypadku stwierdzamy czy szukana wartość jest większa niż na aktualnej pozycji i wtedy zmieniamy a = p + 1. Jeśli nierówność jest w drugą stronę to zmieniamy analogicznie b = p - 1. Jeśli w kolejnej iteracji a > b to szukany element nie istnieje.

Przykład 1

Weźmy tablicę tab = {1, 2, 3, .., 100} z indeksowaniem od 0. Wykorzystując podany algorytm znajdźmy wartość 87. Kolejne kroki wykonywania są następujące:

Element został znaleziony przy pierwszym porównaniu. Jest to zaleta faktu, że tablica to kolejne liczby całkowite. Dzięki temu wyliczanie przybliżonej pozycji elementu jest bardzo dokładne.

Przykład 2

Tym razem niech tablica składa się z 10 elementów: {1, 2, 4, 5, 7, 8, 10, 11, 13, 14}. Jak można zauważyć jest to rozkład prawie liniowy, ale brakuje wielokrotności 3. Tym razem będziemy szukać wartości x = 10:

Pomimo faktu, że rozkład nie ma kolejnych liczb, ale wartości pomiędzy kolejnymi wyrazami nie są zbyt odległe od siebie to algorytm wyliczył pozycję szukanego elementu w pierwszym wyszukiwaniu.

Przykład 3

Jak kolejny przykład warto się przyjrzeć przypadkowi, gdy w tablicy wartości można podzielić na grupki kolejnych liczb, gdzie różnica pomiędzy grupkami jest bardzo duża. Tym razem niech tablica składa się z 9 elementów: {1, 2, 3, 10, 20, 30, 100, 200, 300}. Szukana wartość to x = 100:

Jak można zauważyć dla zaledwie 9 elementowej tablicy trzeba było wykonać cztery porównania. Jest to spowodowane faktem, że duża rozbieżność pomiędzy najmniejszym i największym elementem utrudniały wyliczenie potencjalnej pozycji. Już po pierwszym porównaniu poszukiwania odbywały się w lewej części tablicy zamiast prawej, gdzie szukana wartość się znajdowała. Innymi słowy algorytm Interpolacyjny może być bardzo szybki, ale tylko w szczególnych przypadkach.

Implementacja

Poniżej znajduje się przykładowa implementacja, która zakłada poprawność danych wejściowych tj. tablica jest posortowana.

1. int wyszukaj(int* tab, int n, int x) {
2.   int a = 0, b = n - 1;
3.   while (a <= b) {
4.     int p = a + (x - tab[a])*(b - a) / (tab[b] - tab[a]);
5.     if (tab[p] == x)
6.       return p;
7.     if (tab[p] < x)
8.       a = p + 1;
9.     else
10.       b = p - 1;
11.   }

Funkcja wyszukaj() przyjmuje trzy argumenty tab - tablica liczb, n - długość tablicy oraz x - szukany element. Kolejne kroki (2. - 12.) odpowiadają dokładnie algorytmowi wyszukiwania podanym na początku artykułu. (13.) Wartość -1 jest zwracana, gdy szukany element nie występuje w tablicy.

Testowanie funkcji

W celu przetestowania napisanej funkcji można skorzystać z poniższego fragmentu kodu:

1. int main() {
2.   int n, x;
3.   cout << "Podaj ile tablica ma elementow n = ";
4.   cin >> n;
5.   cout << "Wpisz kolejne elementy:\n";
6.   int* tab = new int[n];
7.   for (int i = 0; i < n; i++)
8.     cin >> tab[i];
9.   cout << "Podaj szukany element x = ";
10.   cin >> x;
11.   int p = wyszukaj(tab, n, x);
12.   if (p == -1) {
13.     cout << "Szukany element nie występuje";
14.   } else {
15.     cout << "Szukany element jest na pozycji " << p;
16.   }
17.   system("pause");
18.   return 0;
19. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Przyjmijmy, że program ma wyszukiwać konkretnej wartości w tablicy posortowanej malejąco używają wyszukiwania Interpolacyjnego. Przykładowa tablica to {3, 2, 1}.

Napisz wersję programu, która będzie wczytywała dane od użytkownika tj. długość tablicy, jej wartości oraz szukany element. Podczas wczytywania danych program ma sprawdzić poprawność wprowadzonych danych. Dodatkowo przed wyliczeniem pozycji p sprawdź czy istnieje szansa, że w podanym zakresie występuje szukana wartość. Przetestuj napisany program.

• Kod źródłowy Zadanie 1