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. static int[] utworzPrzesuniecia(int n) {
2.   int ile = (int)(Math.Ceiling(Math.Log(n, 2.0) + 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. static 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. static void Main(string[] args) {
2.   Console.Write("Podaj ilość elementów na liście\nn = ");
3.   int n = Convert.ToInt32(Console.ReadLine());
4.   int[] a = new int[n];
5.   Console.Write("Podaj elementy listy posortowane rosnąco:\n");
6.   for (int i = 0; i < n; ++i)
7.     a[i] = Convert.ToInt32(Console.ReadLine());
8.   int[] przes = utworzPrzesuniecia(n);
9.   for (int i = 0; i < 20; ++i) {
10.     int poz = wyszukiwanieJednolite(a, i, przes);
11.     Console.Write("Element {0} ", i);
12.     if (poz == -1) {
13.       Console.WriteLine("nie występuje w tablicy");
14.     } else {
15.       Console.WriteLine("jest na pozycji i = {0}", poz);
16.     }
17.   }
18.   Console.ReadKey();
19. }

• 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