Wyszukiwanie binarne


Tematy pokrewne
Tablice – wektory
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
Zliczanie wg kryterium
Wyszukiwanie max lub min
Jednoczesne wyszukiwanie max i min
Zastosowania wyszukiwania – sortowanie przez wybór
Wyszukiwanie najczęstszej wartości w zbiorze – dominanta
Wyszukiwanie lidera
Wyszukiwanie binarne
Wyszukiwanie interpolacyjne
Wyszukiwanie k-tego największego elementu
Wyszukiwanie szybkie k-tego największego elementu
Wyszukiwanie mediany zbioru
Zbiory rozłączne – implementacja w tablicy
Sumy prefiksowe
Wbudowane generatory liczb pseudolosowych

 

Problem

W posortowanym rosnąco zbiorze Z wyszukać element o wartości (kluczu) k.

 

 

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:

 

ip – indeks pierwszego elementu zbioru
ik – indeks końcowego elementu zbioru

indeksy elementów tablicy Z 0 1 2 ... n-2 n-1  
indeksy początku i końca ip         ik  

 

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

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

 

isr =   ip + ik  
2

 

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

 

Z[0] Z[1] ... Z[isr-1] Z[isr] Z[isr+1] ... Z[n-2] Z[n-1]
ip isr ik
elementy ≤ Z[isr]   elementy ≥ Z[isr]

 

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

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

 

Algorytm wyszukiwania binarnego

Wejście
ip  –  indeks pierwszego elementu w tablicy Z, ip C
ik  – indeks ostatniego elementu w tablicy Z, ik C
Z  – tablica do wyszukania elementu. Indeksy od ip do ik
k  – wartość poszukiwanego elementu – tzw. klucz
Wyjście:

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

Zmienne pomocnicze
isr  –  indeks elementu środkowego. isr C
Lista kroków:
K01: p ← -1 ; zakładamy, iż k nie występuje w zbiorze
K02: Dopóki ipik wykonuj K02...K10 ; w pętli poszukujemy elementu o wartości k
K03:
    isr =   ip + ik  
2
; wyznaczamy element środkowy
K04:     Jeśli k ≠ Z[isr], to idź do K07  
K05:     pisr ; element znaleziony, kończymy
K06:     Idź do K11  
K07:     Jeśli k < Z[isr], to idź do K10 ; wybieramy odpowiednią połówkę zbioru na dalsze poszukiwania
K08:     ipisr + 1 ; k > Z[isr] → druga połówka
K09:     Następny obieg pętli K02  
K10:     ikisr - 1 ; k < Z[isr] → pierwsza połówka
K11: Zakończ z wynikiem p  

 

Program

Ważne:

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

 

Lazarus
// Wyszukiwanie binarne
// Data:   7.05.2008
// (C)2012 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.
Code::Blocks
// Wyszukiwanie binarne
// Data:   7.05.2008
// (C)2012 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;
}
Free Basic
' Wyszukiwanie binarne
' Data:   7.05.2008
' (C)2012 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

 

Wyszukiwanie binarne
(C)2012 mgr Jerzy Wałaszek


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.