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

Wyszukiwanie skokowe

https://mattomatti.com/fp03

Opis

Wyszukiwanie skokowe jest to algorytm wyszukujący, który można używać do wyszukiwania danych w posortowanej liście danych. Tak samo jak w przypadku wyszukiwania binarnego głównym celem algorytmu jest wykonanie jak najmniejszej ilości kroków do znalezienia żądanego obiektu. Algorytmy te korzystają z przechodniości uporządkowanych danych. Dla danych uporządkowanych rosnąco oznacza to, że jeśli i-ty element jest mniejszy od następnego to każdy kolejny też jest większy od i-tego.

Przyjmijmy, że na liście L o długości n szukamy wartości x. Wyszukiwanie skokowe polega na podzieleniu listy na bloki równej długości wynoszące m = √n. Następnie sprawdzając pierwsze elementy każdego z bloków należy określić blok w którym szukany element może wystąpić. Innymi słowy należy znaleźć takie k, aby element k·m ≤ x ≤ (k + 1)·m. Po znalezieniu odpowiedniego bloku należy skorzystać z wyszukiwania liniowego w celu znalezienia szukanej wartości w bloku. Element nie istnieje na liście jeśli nie istnieje blok spełniający wymagania. albo podczas wyszukiwania liniowego element nie zostaje również odnaleziony.

Przykład

Weźmy listę elementów L = {4, 7, 8, 13, 18, 20}. Szukamy elementu x = 13. Długość listy to n = 6. Długość bloku to zaokrąglony w dół pierwiastek z 6 czyli m = 2. Lista zostaje podzielona na trzy równe bloki: {{4, 7}, {8, 13}, {18, 20}}. Teraz przechodzimy do wyszukiwania bloku. Dla k = 1 wartość x = 13 ≥ 4, ale nie x ≤ 8. W następnym bloku dla k = 2 spełnione są obie zależności: 8 ≤ x ≤ 18. Teraz należy liniowo przeszukać listę {8, 13}. Oczywiście na koniec należy zwrócić indeks elementu 13 na wybranym fragmencie listy dodany do indeksu pozycji podlisty w liście L. W tym przypadku poprawnym wynikiem jest 3.

Złożoność

Algorytm wyszukiwania skokowego dzieli na bloki o długości m = √n. Oznacza to, że jest maksymalnie m bloków po m wartości. W najgorszym przypadku do sprawdzenie jest m pierwszych elementów każdego bloku i m elementów w bloku czyli złożoność algorytmu to Θ(m + m) = Θ(√n). Jest to wynik pomiędzy złożonością wyszukiwania liniowego Θ(n), a wyszukiwania binarnego Θ(nlog(n)). Algorytm ten jest jednak wykorzystywany wszędzie tam gdzie wracanie do poprzednich elementów jest kosztowne (np. kolejka), ponieważ podczas wyszukiwania cofamy się maksymalnie raz (o m elementów). W przypadku wyszukiwania binarnego można się cofać nawet log n razy.

Implementacja

Funkcja główna

Zgodnie z opisem algorytmu można wyszczególnić trzy etapy: [1] wyszukiwanie bloku gdzie może być element, [2] wyszukiwanie liniowe w bloku, a na koniec [3] sprawdzenie znalezionego elementu. Funkcja wyszukująca sortuje posortowaną listę liczb całkowitych typu int i należy jej podać następujące argumenty: lista - lista danych, n - długość listy oraz find - wartość szukanego elementu.

  1. int searchJump(int* lista, int n, int find) {
  2.   int block = (int)(sqrt(n));
  3.   int index = 0;
  4.   while (lista[min(block, n) - 1] < find) {
  5.     index = block;
  6.     block += (int)(sqrt(n));
  7.     if (index >= n)
  8.       return -1;
  9.   }
  10.   while (lista[index] < find) {
  11.     index++;
  12.     if (index == min(block, n)) {
  13.       return -1;
  14.     }
  15.   }
  16.   if (lista[index] == find)
  17.     return index;
  18.   return -1;
  19. }

(2.) Obliczanie długości bloku i (3.) ustawienie indeksu wyszukiwania na początek listy. (4. - 9.) Dopóki nie znajdziesz odpowiedniego bloku przechodź do następnego. Ważny jest tu warunek stopu, gdy (7.) index wykroczy poza zakres tablicy. W momencie znalezienia odpowiedniego bloku należy (10. - 15.) rozpocząć przeszukiwanie liniowe. Tutaj też istnieje możliwość wyjścia poza blok, ponieważ ostatni blok może mieć mniej elementów niż m, dlatego (12. - 14.) w przypadku wykroczenia należy pamiętać o przerwaniu wyszukiwania. Na sam koniec pozostaje (15.) sprawdzenie czy na wyznaczonym indeksie jest szukany element. Jeśli tak to (16.) zwracamy index, a w przeciwnym razie -1 jako sygnał, że element nie istnieje.

Funkcja pomocnicza

W implementacji została dopisana prosta funkcja min(), która przyjmuje dwa argumenty i zwraca mniejszy z nich.

  1. int min(int a, int b) {
  2.   return (a < b) ? a : b;
  3. }

Testowanie funkcji

W celu przetestowania napisanej funkcji można skorzystać z poniższej funkcji main(). Dane wejściowe można zmieniać modyfikując odpowiednio zmienne n, lista oraz find.

  1. int main () {
  2.   int n = 5;
  3.   int lista[] = { 1, 2, 3, 4, 5 };
  4.   int find = 2;
  5.   cout << "Element " << find << " jest pod indeksem ";
  6.   cout << searchJump(lista, n, find);
  7.   system("pause");
  8.   return 0;
  9. }

Zadania

Zadanie 1

Napisz wersję algorytmu, który znajdzie żądany element wykorzystując do tego rekurencję. Zakładamy, że funkcja po znalezieniu odpowiedniego bloku wywoła samą siebie i uzna znaleziony blok za daną listę. Uwaga: Lista nie powinna być kopiowana do nowej zmiennej.