Strona główna » Algorytmy » Wyszukiwanie » Jednolite Wyszukiwanie Binarne
 

Jednolite Wyszukiwanie Binarne

Cel

Algorytmu Jednolitego Wyszukiwania Binarnego używa się w przypadku, gdy dane na liście będą wyszukiwane wielokrotnie lub na tablicach o równej długości. Proces wyszukiwania danych jest przyśpieszony dzięki zastosowania tablicowania. Ponadto w trakcie wyszukiwania nie ma górnej i dolnej krawędzi wyszukiwania jak w przypadku Wyszukiwania Binarnego. Proces wyszukiwania opiera się na przesuwania o kolejne wartości z wyliczonej wcześniej dodatkowej tablicy.

Działanie na przykładzie

Przypuśćmy, że mamy pewną listę L = {1, 2, 4, 6, 9, 13, 16, 18, 19, 20} o długości n = 10. Pierwszy etap polega na przeprowadzeniu tablicowania. Polega to na przygotowaniu o ile w każdej kolejnej iteracji ma się przesuwać wskaźnik na liście w celu znalezionej wartości. Ma to związek z zawężaniem przestrzeni wyszukiwania w której może znaleźć się wynik. W wyszukiwaniu binarnym w każdej iteracji przedział zwężał się o połowę aktualnej ilości elementów. W tym przypadku kolejne wartości na tworzonej tablicy odpowiadają przejściom pomiędzy kolejnymi środkami przedziałów. Zastosowanie metody tablicowania pozwala na zaoszczędzeniu mocy komputera potrzebnej do ponownego wyliczania o ile należy przesunąć indeks, aby przeprowadzić dalsze wyszukiwanie.

Tworząc tablice należy skorzystać ze wzoru ai = (n + 2i)/2i + 1. Kolejne wartości są wyliczone dopóki w poprzedniej iteracji na końcu tablicy nie znalazła się wartość 0. W tym przypadku wartość 0 oznacza, że wskaźnika już się nie przesuwa i będzie to oznaczało, że danego elementu w szukanej tablicy nie ma. Dla przedstawionej tablicy L utworzona tablica to będzie P = {5, 3, 1, 1, 0}.

Mają utworzoną tablicę przesunięć można przejść do wyszukiwania elementów. Spróbujmy najpierw odnaleźć element 9. Początkowo podczas wyszukiwania należy aktualny indeks ustawić na środek tablicy w której poszukiwany jest element. Dzięki temu będzie możliwe dojście do elementu o ile istnieje przy użyciu wcześniej przygotowanej tablicy.

Aktualny IndeksWartośćKomentarz
51313 to więcej niż 9, więc przesuwamy się o 5 w lewo
011 to mniej niż 9, więc przesuwamy się o 3 w prawo
366 to mniej niż 9, więc przesuwamy się o 1 w prawo
49zwracamy indeks, element został odnaleziony

Spróbujmy teraz wyszukać wartość 7, która nie występuje w przedstawionej liście L.

Aktualny IndeksWartośćKomentarz
51313 to więcej niż 7, więc przesuwamy się o 5 w lewo
011 to mniej niż 7, więc przesuwamy się o 3 w prawo
366 to mniej niż 7, więc przesuwamy się o 1 w prawo
499 to więcej niż 7, więc przesuwamy się o 1 w lewo
366 to mniej niż 7, więc element nie istnieje, ponieważ następne przesunięcie wynosi 0

Implementacja

Tablicowanie

Funkcja utworzPrzesuniecia() przyjmuje tylko jeden argument n, który oznacza długość tablicy na której będą wyszukiwane elementy. Funkcja zwraca tablicę w której są przygotowane wartości dla kolejnych przesunięć.

C++
C#
  1. int* utworzPrzesuniecia(int n) {
  2.   int ile = ceil(log2(n) + 0.5) + 1;
  3.   int* lista = new int[ile];
  4.   int potega = 1;
  5.   for (int i = 0; i < ile; i++) {
  6.     lista[i] = (n + potega) / (2 * potega);
  7.     potega *= 2;
  8.   }
  9.   return lista;
  10. }

Wyszukiwanie

W celu przeprowadzenia wyszukiwania przy pomocy funkcji wyszukiwanieJednolite() należy podać 3 argumenty: tablice do wyszukiwania elementów a, szukaną wartość el oraz tablicę wyliczonych przesunięć przes.

C++
C#
  1. int wyszukiwanieJednolite(int *a, int el, int* przes) {
  2.   int i = przes[0] - 1;
  3.   int d = 0;
  4.   while (true) {
  5.     if (el == a[i]) {
  6.       return i;
  7.     } else if (przes[d] == 0) {
  8.       return -1;
  9.     } else {
  10.       if (el < a[i]) {
  11.         i -= przes[++d];
  12.       } else {
  13.         i += przes[++d];
  14.       }
  15.     }
  16.   }
  17. }

(2.) Ustawiamy aktualny indeks pośrodku tablicy i (3.) wskazujemy, że kolejne przesunięcie ma być wykonane o wartość pierwszego elementu z tablicy przes. (4.) W nieskończonej pętli sprawdź (5.) czy pod aktualnie wybranym indeksem znajduje się szukany element. Jeśli tak to (6.) zwróć aktualny indeks. W przeciwnym razie (7.) sprawdź czy kolejne przesunięcie wynosi 0. Jeśli tak to (8.) zwróć wartość -1, ponieważ dany element nie występuje w tablicy. Jeśli dotychczas żaden warunek nie został spełniony to znaczy, że będziemy przesuwać aktualny wskaźnik. (10.) Określamy to na podstawie relacji szukane elementu i wartości elementu na pozycji. W zależności od wyniku dokonujemy przesunięcia wskaźnika w prawo lub lewo.

Testowanie programu

Testy funkcji można dokonać używając poniższego fragmentu kodu. Program wczytuje od użytkownika tablice od użytkownika, a następnie szuka na niej wartości od 0 do 19. Dla każdej wartosci wyświetla komunikat na której znajduje się pozycji.

C++
C#
  1. int main() {
  2.   int n;
  3.   cout << "Podaj ilosc elementow na liscie\nn = ";
  4.   cin >> n;
  5.   int* a = new int[n];
  6.   cout << "Podaj elementy listy posortowane rosnaco:\n";
  7.   for (int i = 0; i < n; ++i)
  8.     cin >> a[i];
  9.   int* przes = utworzPrzesuniecia(n);
  10.   for (int i = 0; i < 20; ++i) {
  11.     int poz = wyszukiwanieJednolite(a, i, przes);
  12.     cout << "Element " << i << " ";
  13.     if (poz == -1) {
  14.       cout << "nie wystepuje w tablicy\n";
  15.     } else {
  16.       cout << "jest na pozycji i = " << poz << endl;
  17.     }
  18.   }
  19.   system("pause");
  20.   return 0;
  21. }

Zadania

Zadanie 1

Napisz program tak, aby nie było potrzebne podawanie funkcji wyszukiwanieJednolite() tablicy przesunięć przes było opcjonalne. Ponadto funkcja zamiast szukanej wartości el powinna otrzymać tablicę szukanych wartości i dla każdej z nich podać na której znajduje się pozycji.

Napisz funkcję testującą tak, aby użytkownik mógł określić tablicę w której będą wyszukiwane liczby oraz jakie wartości mają zostać wyszukane.