Wyszukiwanie binarne

algorytm, który w czasie logarytmicznym stwierdza, czy szukany element znajduje się w uporządkowanej tablicy

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.

Wyszukiwanie binarne
ilustracja
Rodzaj Podstawowy algorytm wyszukiwania
Struktura danych tablica
Złożoność
Czasowa
Pamięciowa

Zasada działania algorytmuEdytuj

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.

PseudokodEdytuj

A := [...]      { n-elementowa tablica uporządkowana }
lewo := 1       { indeks początku przedziału }
prawo := n    { indeks końca przedziału - początkowo cała tablica A }

y := poszukiwana wartość
indeks := pusty

while lewo < prawo do
   begin
      środek := (lewo + prawo) div 2; { dzielenie całkowitoliczbowe }
      
      if A[środek] < y then
         lewo := środek + 1
      else
         prawo := środek;
   end;

if A[lewo] = y then
   indeks := lewo
else
   indeks := brak;

Wyszukiwanie interpolacyjneEdytuj

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

BibliografiaEdytuj

  • 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.