Strona główna » Algorytmy » Wyszukiwanie » Wyszukiwanie Interpolacyjne
 

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:

abpPorównanieKomentarz
099(87 - 1)(99 - 0)/(100 - 1) = 86x = 87 < 88 = tab[87]Element został znaleziony

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:

abpPorównanieKomentarz
09(10 - 1)(9 - 0)/(14 - 1) ≈ 610 = tab[6] Element został znaleziony

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:

abpPorównanieKomentarz
08(100 - 1)(8 - 0)/(300 - 1) ≈ 2x = 100 > 3 = tab[2]Element jest większy, więc a = 2 + 1 = 3
383 + (100 - 10)(8 - 3)/(300 - 10) ≈ 4x = 100 > 20 = tab[4]Element jest większy, więc a = 5
585 + (100 - 30)(8 - 5)/(300 - 30) ≈ 5x = 100 > 30 = tab[5]Element jest większy, więc a = 6
686 + (100 - 100)(8 - 6)/(300 - 100) = 6x = 100 = tab[6]Element został znaleziony

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

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.