Wyszukiwanie binarne

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Wyszukiwanie binarne
ilustracja
Rodzaj Podstawowy algorytm wyszukiwania
Struktura danych tablica
Złożoność
Czasowa
Pamięciowa

Wyszukiwanie binarnealgorytm opierający się na metodzie dziel i zwyciężaj, który w czasie logarytmicznym stwierdza, czy szukany element znajduje się w uporządkowanej tablicy i jeśli się znajduje, podaje jego indeks. Np. jeśli tablica zawiera milion elementów, wyszukiwanie binarne musi sprawdzić maksymalnie 20 elementów w celu znalezienia żądanej wartości. Dla porównania wyszukiwanie liniowe wymaga w najgorszym przypadku przejrzenia wszystkich elementów tablicy.

Zasada działania algorytmu[edytuj | edytuj kod]

Uporządkowana tablica jest dzielona na coraz mniejsze przedziały do momentu, gdy przedział osiągnie długość jeden, kiedy możemy jednym sprawdzeniem określić, czy element znajduje się w tablicy.

W pojedynczym kroku rozważa się jeden przedział charakteryzowany dwoma indeksami: początkowym i końcowym Algorytm rozpoczyna wyszukiwanie od całej tablicy.

Następnie wyznaczany jest środek tego przedziału

Przedział jest zawężany – dzięki uporządkowaniu danych wiadomo, że albo poszukiwany element może znajdować się w indeksach albo za nim. Innymi słowy wybór ogranicza się do przedziału gdy poszukiwany element jest mniejszy lub równy zapisanemu pod indeksem albo w przeciwnym razie.

Algorytm kończy się niepowodzeniem, jeśli przedział będzie jednoelementowy, tzn. a pod indeksem nie ma poszukiwanej wartości.

Implementacja[edytuj | edytuj kod]

Zastosowano język TypeScript.

/**
 * Zwraca indeks poszukiwanego elementu
 * lub null jeśli dany element w tablicy nie istnieje.
 *
 * @param tablica - posortowana tablica liczb.
 * @param szukana - poszukiwana wartość.
 */
function wyszukiwanieBinarnie(tablica: number[], szukana: number): number {
    let lewo = 0;
    let prawo = tablica.length - 1;
    let przeszukiwany_indeks;
    
    while (lewo <= prawo) {
        przeszukiwany_indeks = Math.floor((lewo + prawo) / 2);
        if (tablica[przeszukiwany_indeks] < szukana) {
            lewo = przeszukiwany_indeks + 1;
        } else if (tablica[przeszukiwany_indeks] > szukana) {
            prawo = przeszukiwany_indeks - 1;
        } else {
            return przeszukiwany_indeks;
        }
    }
    
    return null;
}


Wyszukiwanie interpolacyjne[edytuj | edytuj kod]

Wariant wyszukiwania binarnego, w którym punkt podziału (indeks ) jest wyznaczany metodą interpolacji liniowej.

Jeśli wartości kluczy na krańcach przedziału wynoszą i i poszukiwana wartość wówczas indeks można wyznaczyć jako gdzie parametr wynika z wartości kluczy:

Algorytm charakteryzuje o wiele lepsza średnia złożoność obliczeniowa niż zwykłego wyszukiwania binarnego, wynosi bowiem a nie Ta złożoność jest osiągana tylko dla danych mających rozkład jednostajny, w przypadku pesymistycznym jest jednak liniowa. Jak podaje Knuth, testy empiryczne wykazują, że podejście to dobrze sprawdza się dla bardzo dużych rozmiarów tablic, dla niewielkich nie widać wyraźnej przewagi ze względu na bardziej złożone wyliczanie indeksu

Pomysłodawcą metody był W.W. Peterson, została użyta do wyszukiwania w posortowanych plikach; została ona opracowana ok. 1957 roku.

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  • Donald Knuth, Sztuka programowania, T. III, Sortowanie i wyszukiwanie, WNT 2002
  • W.W. Peterson. dressing for Random-Access Storage. „IBM Journal of Research and Development”. 1(4), s. 130–146, 1957.