Algorytmy i Struktury Danych - Wyszukiwanie binarne

Postąpimy w sposób następujący.

Wyznaczymy element środkowy zbioru. Sprawdzimy, czy jest on poszukiwanym elementem. Jeśli tak, to element został znaleziony i możemy zakończyć poszukiwania. Jeśli nie, to poszukiwany element jest albo mniejszy od elementu środkowego, albo większy. Ponieważ zbiór jest uporządkowany, to elementy mniejsze od środkowego będą leżały w pierwszej połówce zbioru, a elementy większe w drugiej połówce. Zatem w następnym obiegu zbiór możemy zredukować do pierwszej lub drugiej połówki – jest w nich o połowę mniej elementów. Mając nowy zbiór postępujemy w sposób identyczny – znów wyznaczamy element środkowy, sprawdzamy, czy jest poszukiwanym elementem. Jeśli nie, to zbiór dzielimy znów na dwie połowy – elementy mniejsze od środkowego i elementy większe od środkowego. Poszukiwania kontynuujemy w odpowiedniej połówce zbioru aż znajdziemy poszukiwany element lub do chwili, gdy po podziale połówka zbioru nie zawiera dalszych elementów.

Ponieważ w każdym obiegu pętli algorytm redukuje liczbę elementów o połowę, to jego klasa złożoności obliczeniowej jest równa O ( log n ). Jest to bardzo korzystna złożoność. Na przykład w algorytmie wyszukiwania liniowego przy 1000000 elementów należało wykonać aż 1000000 porównań, aby stwierdzić, iż elementu poszukiwanego nie ma w zbiorze. W naszym algorytmie wystarczy 20 porównań.

Oczywiście algorytm wyszukiwania liniowego może być zastosowany dla dowolnego zbioru. Nasz algorytm można stosować tylko i wyłącznie w zbiorze uporządkowanym. Ze względu na podział zbioru na kolejne połówki, ćwierci itd. algorytm nosi nazwę wyszukiwania binarnego (ang. binary search ).

Musimy uściślić sposób podziału zbioru na coraz mniejsze fragmenty. Zbiór Z odwzorowujemy w tablicy Z składającej się z n elementów ponumerowanych kolejno od 0 do n-1. Określmy dwa indeksy:

i_p – indeks pierwszego elementu zbioru
i_k – indeks końcowego elementu zbioru

indeksy elementów tablicy Z	0	1	2	...	n-2	n-1
indeksy początku i końca	*i_p*					*i_k*

Indeksy i_p i i_k określają obszar zbioru w tablicy Z. Początkowo będą oczywiście równe: i_p = 0 oraz i_k = n - 1.

Na podstawie tych dwóch indeksów obliczamy indeks elementu środkowego i_sr:

Jeśli zbiór Z jest uporządkowany rosnąco, to:

Z [ 0 ]	Z [ 1 ]	...	Z [ i_sr-1 ]	Z [ i_sr ]	Z [ i_sr+1 ]	...	Z [ n-2 ]	Z [ n-1 ]
i_p	←			i_sr	→			i_k
elementy ≤ Z [ i_sr ]					elementy ≥ Z [ i_sr ]

Zatem w przypadku, gdy k < Z [ i_sr ], to przechodzimy do pierwszej połówki, w której indeksy przebiegają od i_p do i_sr - 1. Element Z [ i_sr ] pomijamy, gdyż wiadomo, że o niego nam nie chodzi.

Jeśli k > Z [ i_sr ], to przechodzimy do drugiej połówki o indeksach od i_sr + 1 do i_k.

Algorytm wyszukiwania binarnego

Wejście:

i_p	–	indeks pierwszego elementu w tablicy Z, i_p ∈ C.
i_k	–	indeks ostatniego elementu w tablicy Z, i_k ∈ C.
Z	–	tablica do wyszukania elementu. Indeksy od i_p do i_k.
k	–	wartość poszukiwanego elementu – tzw. klucz.

Wyjście:

p = indeks elementu o kluczu k lub
p = -1, jeśli nie odnaleziono elementu o takim kluczu.

Zmienne pomocnicze:

i_sr

–

indeks elementu środkowego. i_sr ∈ C.

Lista kroków:

K01:	p ← -1	zakładamy, iż k nie występuje w zbiorze
K02:	Dopóki i_p ≤ i_k, wykonuj kroki K02...K10	w pętli poszukujemy elementu o wartości k
K03:		; wyznaczamy element środkowy
K04:	Jeśli k ≠ Z [ i_sr ], to idź do kroku K07
K05:	p ← i_sr	element znaleziony, kończymy
K06:	Idź do kroku K11
K07:	Jeśli k < Z [ i_sr ], to idź do kroku K10	wybieramy odpowiednią połówkę zbioru na dalsze poszukiwania
K08:	i_p ← i_sr + 1	k > Z [ i_sr ] → druga połówka
K09:	Następny obieg pętli K02
K10:	i_k ← i_sr - 1	k < Z [ i_sr ] → pierwsza połówka
K11:	Zakończ z wynikiem p

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program wypełnia tablicę 100 elementową Z liczbami naturalnymi w taki sposób, aby powstał z nich ciąg rosnący. Następnie generuje liczbę pseudolosową k z zakresu od Z [ 0 ] do Z [ 99 ] i wyszukuje binarnie jej położenie w tablicy. Na koniec wyświetlana jest liczba k, jej położenie w Z oraz zawartość tablicy Z z zaznaczonym elementem o wartości k. Jeśli k nie występuje w Z, to zamiast położenia program wyświetla słowo BRAK. Dodatkowo program zlicza wykonane obiegi pętli i wypisuje ich liczbę.

Pascal

// Wyszukiwanie binarne
// Data:   7.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

const N = 100;

var
  Z : array [ 0..N - 1 ] of integer;
  i, ip, ik, isr, k, L, p : integer;

begin
  randomize;

  // wypełniamy tablicę Z [ ] 

  Z [ 0 ] := random ( 5 );
  for i := 1 to N - 1 do Z [ i ] := Z [ i - 1 ] + random ( 5 );

  // generujemy klucz k

  k := Z [ 0 ] + random ( Z [ N - 1 ] - Z [ 0 ] + 1 );

  // poszukujemy binarnie elementu k

  L  := 0; p  := -1; ip := 0; ik := N - 1;
  while ip <= ik do
  begin
    inc ( L );
    isr := ( ip + ik ) shr 1;
    if Z [ isr ] = k then
    begin
      p := isr; break;
    end
    else if k < Z [ isr ] then ik := isr - 1
    else                       ip := isr + 1;
  end;

  // wyświetlamy wyniki

  write ( k, ' : ' );
  if p >= 0 then write ( p ) else write ( 'BRAK' );
  writeln ( ' : obiegi = ', L );
  writeln;
  for i := 0 to N - 1 do
  begin
    write ( Z [ i ] :3 );
    if p = i then write ( '<' ) else write ( ' ' );
  end;
  writeln;
  writeln;
end.

C++

// Wyszukiwanie binarne
// Data:   7.05.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 100;

int main( )
{
  int Z [ N ], i, ip, ik, isr, k, L, p;

  srand ( ( unsigned )time ( NULL ) );

  // wypełniamy tablicę Z [ ] 

  Z [ 0 ] = rand( ) % 5;
  for( i = 1; i < N; i++ ) Z [ i ] = Z [ i - 1 ] + ( rand( ) % 5 );

  // generujemy klucz k

  k = Z [ 0 ] + ( rand( ) % ( Z [ N - 1 ] - Z [ 0 ] + 1 ) );

  // poszukujemy binarnie elementu k

  p = -1; L = ip = 0; ik = N - 1;
  while( ip <= ik )
  {
    L++;
    isr = ( ip + ik ) >> 1;
    if( Z [ isr ] == k )
    {
      p = isr; break;
    }
    else if( k < Z [ isr ] ) ik = isr - 1;
    else                     ip = isr + 1;
  }

  // wyświetlamy wyniki

  cout << k << ": ";
  if( p >= 0 ) cout << p; else cout << "BRAK";
  cout << ": obiegi = " << L << endl << endl;
  for( i = 0; i < N; i++ )
  {
    cout << setw ( 3 ) << Z [ i ];
    if( p == i ) cout << "<"; else cout << " ";
  }
  cout << endl << endl;
  return 0;
}

Basic

' Wyszukiwanie binarne
' Data:   7.05.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Const N = 100

Dim As Integer Z ( N-1 ), i, ip, ik, isr, k, L, p

Randomize

' wypełniamy tablicę Z [ ] 

Z ( 0 ) = Cint ( Rnd * 4 )
For i = 1 To N - 1: Z ( i ) = Z ( i-1 ) + Cint ( Rnd * 4 ): Next

' generujemy klucz k

k = Z ( 0 ) + Cint ( Rnd * ( Z ( N - 1 ) - Z ( 0 ) ) )

' poszukujemy binarnie elementu k

L  = 0: p  = -1: ip = 0: ik = N - 1
While ip <= ik
  L += 1
  isr = ( ip + ik ) Shr 1
  If Z ( isr ) = k Then
    p = isr: Exit While
  Elseif k < Z ( isr ) Then
    ik = isr - 1
  Else
    ip = isr + 1
  End If
Wend

' wyświetlamy wyniki

Print k;": ";
If p >= 0 Then Print p;: Else Print "BRAK";
Print ": obiegi =";L
Print
For i = 0 To N - 1
  Print Using "###";Z ( i );
  If p = i Then Print "<";: Else Print " ";
Next
Print
Print
End

Wynik:

42 : BRAK : obiegi = 7

2 6 10 14 17 17 19 22 23 26 27 27 27 29 32 35 39 43 43 47
47 48 48 49 49 50 53 57 57 58 62 62 63 67 68 72 75 75 77 81
85 86 88 92 94 96 98 100 101 103 105 106 106 109 109 113 115 116 116 116
120 123 125 126 128 128 129 133 137 137 139 142 143 145 149 149 149 149 153 157
161 162 166 167 167 168 169 173 176 180 180 180 180 184 186 186 190 194 198 202

92 : 45 : obiegi = 5

4 6 7 11 14 18 22 23 27 30 33 36 37 37 40 44 47 47 47 47
49 51 53 54 58 62 62 62 62 63 67 69 69 71 71 73 73 77 79 80
83 86 90 91 91 92< 93 93 97 99 99 101 105 107 110 111 111 115 115 115
118 121 122 122 122 126 128 130 130 131 135 136 139 143 145 147 147 151 153 153
154 155 157 160 164 164 168 169 173 174 176 180 183 187 190 193 194 198 198 202

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Wyszukiwanie binarne