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:

i_sr = [(i_p + i_k) / 2]

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, ; w pętli poszukujemy
     wykonuj kroki K02…K10 ; elementu o wartości k
K03:   i_sr = [(i_p + i_k) / 2] ; 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], ; wybieramy odpowiednią połówkę
       to idź do kroku K10 ; 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 <ctime>

using namespace std;

const int N = 100;

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

  srand(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

Python (dodatek)

# Wyszukiwanie binarne
# Data:  27.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random

N = 100 # Liczba elementów
Z = []  # Tablica

# wypełniamy tablicę Z[]

Z.append(random.randrange(5))
for i in range(1,N):
    Z.append(Z[i-1] + random.randrange(5))

# generujemy klucz k

k = random.randrange(Z[0],Z[N-1] + 1)

# poszukujemy binarnie elementu k

L,p,ip,ik = 0,-1,0,N - 1
while ip <= ik:
    L += 1
    isr = (ip + ik) >> 1
    if Z[isr] == k:
        p = isr
        break
    elif k < Z[isr]:
        ik = isr - 1
    else:
        ip = isr + 1
   
# wyświetlamy wyniki

print(k,": ", end="")
if p >= 0:
    print(p, end="")
else:
    print("BRAK", end="")
print(" : obiegi =",L)
print()
for i in range(N):
    print("%3d" % Z[i], end="")
    if p == i:
        print("<", end="")
    else:
        print(" ", end="")
print()
print()

Wynik:

6 : BRAK : obiegi = 6

   0   0   0   3   5   5   9  13  15  16  18  22  24  26  30  33  37  41  43  47
  47  47  49  52  55  56  56  58  58  58  62  66  66  70  74  74  75  75  75  77
  80  84  86  86  88  90  93  94  94  98 100 102 106 108 110 111 115 117 118 119
 120 120 121 124 125 127 131 131 135 139 142 145 146 146 146 146 146 148 152 155
 158 158 159 159 161 165 168 169 169 172 174 177 179 182 186 186 187 187 188 190

192 : 88 : obiegi = 6

1 3 7 8 11 14 14 14 16 19 19 22 25 28 28 28 31 32 34 36
39 39 43 46 47 47 51 51 52 56 60 64 67 70 72 74 76 78 79 83
86 89 89 91 92 92 92 95 95 96 97 98 101 104 105 108 109 112 115 117
121 125 125 126 128 131 135 137 139 141 144 147 151 151 154 158 159 163 167 169
173 177 181 183 185 185 186 188 192<194 198 200 204 208 208 209 209 209 209 210

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