Oferty pracy dla inżynierów
  • StrefaInzyniera.pl (current)
  • Oferty pracy
  • Automatyka
    • Uprawnienia elektryczne SEP
    • Elektrotechnika
    • Elektronika
    • Automatyka
    • Robotyka
  • PrzemysÅ‚
    • PrzemysÅ‚
    • Obróbka metali
    • CAD
    • CATIA
    • Autodesk Inventor
  • IT
    • JAVA
    • C++
    • Sieci
  • Firmy
  • Dla firm
    • Rejestracja - profil firmy
    • Dodaj ofertÄ™ pracy - bezpÅ‚atnie
    • Publikacja artykułów
    • Kontakt
  • Zaloguj siÄ™
  • STREFA INÅ»YNIERA
  • Oferty pracy
  • Automatyka
    • Uprawnienia elektryczne SEP
    • Elektrotechnika
    • Elektroniki
    • Automatyki
    • Robotyka
  • PrzemysÅ‚
    • PrzemysÅ‚
    • Obróbka metali
    • CAD
    • CATIA
    • Autodesk Inventor
  • IT
    • JAVA
    • C++
    • Sieci
  • Firmy
  • Dla firm
    • Rejestracja - profil firmy
    • Dodaj ofertÄ™ pracy - bezpÅ‚atnie
    • Publikacja artykułów
    • Kontakt
  • Logowanie
  • Zaloguj siÄ™
Wyszukiwanie binarne
Categories

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:

2 3 5 10 27 30 34 51 56 65 77 81 82 93 99

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:

56 65 77 81 82 93 99

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.

 

1 // Rysunek 19.3. BinarySearchTest.java
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 }

 

[13, 18, 29, 36, 42, 47, 56, 57, 63, 68, 80, 81, 82, 88, 88]
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

Zaloguj się aby dodać komentarz

Podobne artykuły

« Sortowanie przez wstawianieWyszukiwanie liniowe »

Podziel się ze znajomymi tym artykułem - udostępnij na FB lub wyślij e-maila korzystając z poniższych opcji:

Oferty pracy dla inżynierów
Oferty pracy dla inżynierów

Elektryk automatyk

Guz Technika Piekarnicza
Siemianowice Śląskie, śląskie
4500-6500 PLN

Product Engineer

SPX Flow Inc.
Bydgoszcz, kujawsko-pomorskie

Inżynier ds. Rozwoju Platform i Aplikacji Telewizyjnych

Play (P4 sp. zo.o.)
Warszawa, mazowieckie

Starszy Inżynier ds. Rozwoju Platform Strumieniowania i Dystrybucji Wideo

Play (P4 sp. zo.o.)
Warszawa, dowolny Region

Inżynier ds. Rozwoju Urządzeń Abonenckich – Smartfony, Tablety, Urządzenia Wearables

Play (P4 sp. zo.o.)
Warszawa, dowolny Region

Ekspert ds. Rozwoju Urządzeń Abonenckich STB

Play (P4 sp. zo.o.)
Warszawa, dowolny Region

wszystkie oferty
PracaTechniczna.pl

Strefainzyniera.pl - rynek, praca, rozwój - wszystko co ważne dla inżynierów

  • Dla pracodawcy
  • ArtykuÅ‚y
  • Praca
  • Publikacje
  • Popularne stanowiska
  • Offer in English
  • Regulamin
  • Regulamin dla klientów
  • Polityka prywatnoÅ›ci
  • Polityka cookies
  • Kontakt

© 2011 - 2021 NetPortal

Mapa strony Letnisko blisko