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.