Wyszukiwanie binarne
Algorytm wyszukiwania binarnego jest bardziej wydajny niż wyszukiwanie liniowe, ale wymaga posortowanej tablicy. Pierwsza iteracja algorytmu sprawdza element środkowy tablicy. Jeśli klucz wyszukiwania pasuje, algorytm kończy działanie. Przy założeniu, że tablica jest posortowana rosnąco, jeżeli szukany klucz jest mniejszy od elementu środkowego, nie może znajdować się w drugiej połowie tablicy, więc algorytm kontynuuje działanie tylko z pierwszą połową (od pierwszego elementu do środkowego, ale bez środkowego). Jeżeli szukany klucz jest większy od elementu środkowego, nie może znajdować się w pierwszej połowie tablicy, więc algorytm kontynuuje działanie tylko z drugą połową (od elementu za środkiem do końca tablicy). Każda iteracja zaczyna się od sprawdzenia środka pozostałej części tablicy. Jeśli klucz wyszukiwania nie jest równy środkowi, algorytm eliminuje połowę tablicy. Algorytm albo znajdzie pasujący element, albo zredukuje długość tablicy do 0.
Przykład
Jako przykład niech posłuży nam piętnastoelementowa tablica:
i klucz wyszukiwania wynoszący 65. Program implementujący algorytm wyszukiwania binarnego najpierw sprawdzi, czy 51 jest kluczem wyszukiwania (ponieważ 51 to środkowy element tablicy). Klucz wyszukiwania (65) jest większy od 51, więc ignorujemy 51 wraz z pierwszą połową tablicy (wszystkie elementy mniejsze od 51). Pozostaje nam:
Teraz algorytm sprawdza, czy 81 (środek pozostałej części tablicy) pasuje do klucza wyszukiwania. Klucz wyszukiwania (65) jest mniejszy od 81, więc 81 pomijamy wraz z elementami większymi od 81. Po tylko dwóch testach algorytm ograniczył do trzech (56, 65 i 77) liczbę wartości do sprawdzenia. Sprawdza teraz 65 (wartość pasuje do klucza), więc zwraca indeks elementu zawierającego 65. Algorytm wymagał tylko trzech porównań, aby określić, gdzie w tablicy znajduje się poszukiwany element. Algorytm wyszukujący liniowo wymagałby dziesięciu porównań. (Uwaga: W przykładzie wybraliśmy nieparzystą liczbę elementów, więc zawsze będzie istniał oczywisty środek. W przypadku tablicy o parzystej liczbie elementów środek tablicy znajduje się między dwoma elementami. Zaimplementujemy algorytm, który wybiera większy z nich).
Implementacja wyszukiwania binarnego
Klasa BinarySearchTest (rysunek 19.3) zawiera:
- metodę statyczną binarySearch wyszukującą w tablicy typu int konkretnego klucza;
- metodę statyczną remainingElements, która wyświetla pozostałe elementy przeszukiwanej tablicy;
- metodę main testującą binarySearch.
2 // Użycie wyszukiwania binarnego do znalezienia elementu tablicy
3 import java.security.SecureRandom;
4 import java.util.Arrays;
5 import java.util.Scanner;
6
7 public class BinarySearchTest {
8 // Wykonuje wyszukiwanie binarne na zbiorze danych
9 public static int binarySearch(int[] data, int key) {
10 int low = 0; // Dolna część obszaru wyszukiwania
11 int high = data.length - 1; // Górna część obszaru wyszukiwania
12 int middle = (low + high + 1) / 2; // Element środkowy
13 int location = -1; // Zwracana wartość; -1, jeśli elementu nie znaleziono
14
15 do { // Pętla poszukująca elementu
16 // Wyświetl pozostałe elementy tablicy
17 System.out.print(remainingElements(data, low, high));
18
19 // Spacje odpowiadają za wyrównywanie
20 for (int i = 0; i < middle; i++) {
21 System.out.print(" ");
22 }
23 System.out.println(" * "); // Wskaż element środkowy
24
25 // Jeśli element znajduje się na środku
26 if (key == data[middle]) {
27 location = middle; // Położenie to aktualny środek
28 }
29 else if (key < data[middle]) { // Środek jest za duży
30 high = middle - 1; // Wyeliminuj drugą połowę
31 }
32 else { // Środek jest za mały
33 low = middle + 1; // Wyeliminuj pierwszą połowę
34 }
35
36 middle = (low + high + 1) / 2; // Oblicz środek
37 } while ((low <= high) && (location == -1));
38
39 return location; // Zwróć położenie klucza wyszukiwania
40 }
41
42 // Metoda wyświetlająca pewne wartości z tablicy
43 private static String remainingElements(
44 int[] data, int low, int high) {
45 StringBuilder temporary = new StringBuilder();
46
47 // Dodaj spacje w celu wyrównania
48 for (int i = 0; i < low; i++) {
49 temporary.append(" ");
50 }
51
52 // Dodaj elementy pozostałe w tablicy
53 for (int i = low; i <= high; i++) {
54 temporary.append(data[i] + " ");
55 }
56
57 return String.format("%s%n", temporary);
58 }
59
60 public static void main(String[] args) {
61 Scanner input = new Scanner(System.in);
62 SecureRandom generator = new SecureRandom();
63
64 // Utwórz tablicę 15 losowych i posortowanych liczb całkowitych
65 int[] data = generator.ints(15, 10, 100).sorted().toArray();
66 System.out.printf("%s%n%n", Arrays.toString(data)); // Wyświetl tablicę
67
68 // Pobranie danych od użytkownika
69 System.out.print("Wpisz liczbę całkowitą (-1, aby zakończyć): ");
70 int searchInt = input.nextInt();
71
72 // Pobieranie w pętli liczby całkowitej; -1 przerywa program
73 while (searchInt != -1) {
74 // Wykonaj wyszukiwanie
75 int location = binarySearch(data, searchInt);
76
77 if (location == -1) { // Nie znaleziono
78 System.out.printf("%d nie znaleziono%n%n", searchInt);
79 }
80 else { // Znaleziono
81 System.out.printf("%d znaleziono na pozycji %d%n%n",
82 searchInt, location);
83 }
84
85 // Pobranie danych od użytkownika
86 System.out.print("Wpisz liczbę całkowitą (-1, aby zakończyć): ");
87 searchInt = input.nextInt();
88 }
89 }
90 }
Wpisz liczbę całkowitą (-1, aby zakończyć): 18
13 18 29 36 42 47 56 57 63 68 80 81 82 88 88
*
13 18 29 36 42 47 56
*
13 18 29
*
18 znaleziono na pozycji 1
Wpisz liczbę całkowitą (-1, aby zakończyć): 82
13 18 29 36 42 47 56 57 63 68 80 81 82 88 88
*
63 68 80 81 82 88 88
*
82 88 88
*
82
*
82 znaleziono na pozycji 12
Wpisz liczbę całkowitą (-1, aby zakończyć): 69
13 18 29 36 42 47 56 57 63 68 80 81 82 88 88
*
63 68 80 81 82 88 88
*
63 68 80
*
80
*
69 nie znaleziono
Wpisz liczbę całkowitą (-1, aby zakończyć): -1
Rysunek 19.3. Użycie wyszukiwania binarnego do znalezienia elementu tablicy
Metoda main (wiersze od 60. do 89.) jest prawie taka sama jak metoda main z rysunku 19.2. W tym programie wiersz 65. tworzy strumień z 15 losowymi elementami (Java SE 8), sortuje wartości rosnąco i konwertuje strumień na tablicę wartości int. Przypomnijmy, że algorytm wyszukiwania binarnego zadziała tylko dla posortowanych tablic. Pierwszy wiersz wyników przedstawia posortowaną tablicę liczb. Gdy użytkownik prosi o wyszukanie liczby 18, program sprawdza najpierw element środkowy, którym jest 57 (wskazywany przez *). Klucz wyszukiwania jest mniejszy od 57, więc program eliminuje drugą połowę tablicy i sprawdza
ponownie pierwszą połowę. Klucz wyszukiwania jest mniejszy od 36, więc program eliminuje ponownie drugą połowę, co powoduje, że pozostają tylko trzy elementy. Teraz program sprawdza 18 (które pasuje do klucza wyszukiwania),
więc zwraca indeks 1.
Wiersze od 9. do 40. deklarują metodę binarySearch, która otrzymuje jako parametry tablicę do wyszukania (key) i klucz wyszukiwania (key). Wiersze od 10. do 12. obliczają indeks dolny (low), górny (high) i środek (middle) w tablicy aktualnie przeszukiwanej przez program. Na początku metody low wynosi 0, a high jest równy długości tablicy minus 1. Wartość middle stanowi średnia tych dwóch wartości. Wiersz 13. inicjalizuje położenie elementu (location) na -1 — wartość, która zostanie zwrócona, jeśli nie znaleziono key. Wiersze od 15. do 37. wykonują się w pętli aż do momentu, w którym low stanie się większe od high (czyli gdy nie znaleziono klucza). Wiersz 26. sprawdza, czy wartość elementu middle jest równa key. Jeśli tak, wiersz 27. przypisuje middle do location, pętla jest przerywana i location jest zwracane do kodu wywołującego. Każda iteracja
pętli sprawdza pojedynczą wartość (wiersz 26.) i eliminuje połowę wartości z tablicy (wiersze od 29. do 31. i od 32. do 34.), jeżeli wartość nie jest kluczem (key).
Wydajność wyszukiwania binarnego
W najgorszym przypadku przeszukanie posortowanej tablicy 1023 elementów wymaga tylko 10 porównań, jeśli stosujemy wyszukiwanie binarne. Wykonując za każdym razem dzielenie 1023 przez 2 (po każdym sprawdzeniu eliminujemy połowę tablicy) i zaokrąglając w dół (bo usuwamy też element środkowy), otrzymujemy wartości 511, 255, 127, 63, 31, 15, 7, 3, 1 i 0. Liczba 1023 (210 – 1) jest podzielna przez 2 jedynie 10 razy do momentu otrzymania 0, które wskazuje na brak elementów do sprawdzenia. Dzielenie przez 2 jest równoważne jednemu porównaniu algorytmu. Oznacza to, że tablica z 1 048 575 (220 – 1) elementami wymaga maksymalnie 20 porównań, aby znaleźć klucz, a tablica z miliardem elementów wymaga tylko 30 porównań, aby znaleźć klucz. To znacząca poprawa względem wyszukiwania liniowego. W przypadku miliarda elementów to różnica między 500 milionami porównań dla wyszukiwania liniowego i maksymalnie 30 dla wyszukiwania binarnego! Maksymalna liczba porównań wymagana
przez algorytm dla wyszukiwania w posortowanej tablicy to wykładnik pierwszej potęgi 2 większej od liczby elementów tablicy, co reprezentuje zapis log2 n. Wszystkie algorytmy rosną w podobnym tempie, więc w notacji dużego O pomijamy bazę. Oznacza to, że algorytm sortowania binarnego to O(log n), czyli algorytm o logarytmicznym czasie wykonania.
Programowanie w Javie. Solidna wiedza w praktyce. Wydanie XI, Autorzy: Paul Deitel, Harvey Deitel, Wydawnictwo: Helion
