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 a_i = (n + 2ⁱ)/2^{i + 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.

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

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ęć.

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.

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.

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

• Kod źródłowy Implementacja

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.

• Kod źródłowy Zadanie 1