Materiały pomocnicze:

Tablice i podstawowe operacje na tablicach
Wskaźniki i tablice dynamiczne
Przeszukiwanie liniowe oraz liniowe z wartownikiem
 

Wyszukiwanie binarne

Wyszukiwanie liniowe (lub liniowe z wartownikiem) stosowane jest dla zbiorów nieuporządkowanych. W takich zbiorach nic nie możemy założyć na temat położenia poszukiwanego elementu - może on się znajdować na początku, w środku lub na końcu zbioru. Aby go znaleźć należy po kolei przeglądnąć wszystkie elementy. Algorytmy wyszukiwania liniowego posiadają liniową klasę złożoności obliczeniowej O(n).

Sytuacja się zmienia, gdy mamy do czynienia ze zbiorem uporządkowanym. W takim zbiorze elementy występują w określonej kolejności. Załóżmy, że szukamy elementu o wartości v. Wybieramy ze zbioru uporządkowanego element środkowy, oznaczmy go es. Jeśli v = es, to znaleźliśmy poszukiwany element i możemy zwrócić jego pozycję, kończąc wykonanie poszukiwania. Jeśli równość nie zachodzi, to musi zajść jedna z dwóch nierówności:

  1. v < es - element poszukiwany może być w pierwszej połówce. W drugiej nie, ponieważ, ze względu na uporządkowanie zbioru, elementy drugiej połówki są większe lub równe es.

  2. v > es - element poszukiwany może być w drugiej połówce. Elementy pierwszej połówki zbioru są od niego mniejsze.

Zatem po pierwszym teście ograniczamy liczbę elementów zbioru do połowy - pomijamy całą połówkę zbioru. Wybraną połówkę zbioru przyjmujemy za nowy zbiór i operację powtarzamy dotąd, aż znajdziemy poszukiwaną wartość, lub otrzymamy jako wynik zbiór pusty - elementu brak w zbiorze. Ponieważ przy każdym obiegu ilość elementów do przeszukania zmniejsza się o połowę, to taki algorytm, zwany wyszukiwaniem binarnym (ang. binary search), posiada klasę złożoności obliczeniowej O(log n). Jest ona bardzo korzystna. Przykładowo, algorytm liniowy w zbiorze 256 elementowym musiał wykonać 256 testów, aby stwierdzić, że poszukiwanego elementu brak. Tymczasem algorytm wyszukiwania binarnego dojdzie do tego samego wyniku już po 8 testach - czysty zysk.

Musimy uściślić sposób podziału zbioru na coraz mniejsze fragmenty. Zbiór odwzorowujemy w tablicy T[ ] 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 T[ ] 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 T[ ]. 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 is:

 

is =   ip  + ik   
2

 

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

 

T[0] T[1] ... T[is-1] T[is] T[is+1] ... T[n-2] T[n-1]
ip is ik
elementy ≤ T[is]   elementy ≥ T[is]

 

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

Jeśli v  > T[is], to przechodzimy do drugiej połówki o indeksach od is  + 1 do ik. Pusty zbiór otrzymamy, gdy indeksy ip  oraz ik miną się, tzn. ip > ik.

 

Algorytm wyszukiwania binarnego

Wejście
ip  -  indeks pierwszego elementu w tablicy T[ ], ip  ∈C
ik  - indeks ostatniego elementu w tablicy T[ ], ikC
T[ ]  - tablica do wyszukania elementu. Indeksy od ip  do ik 
v  - wartość poszukiwanego elementu
Wyjście:

p  = indeks elementu o wartości v
p
  = -1, jeśli nie odnalezienia elementu o wartości v

Zmienne pomocnicze
is  -  indeks elementu środkowego. isC
Lista kroków:
Krok 1: p  ← -1 ; zakładamy, iż v nie występuje w zbiorze
Krok 2: Jeśli ip  > ik  to zakończ ; w pętli poszukujemy elementu o wartości v
Krok 3:
is =   ip  + ik   
2
; wyznaczamy element środkowy
Krok 4: Jeśli v ≠ T[is], to idź do kroku 7  
Krok 5: p  ← is ; element znaleziony, kończymy
Krok 6: Zakończ  
Krok 7: Jeśli v  < T[isr], to idź do kroku 10 ; wybieramy odpowiednią połówkę zbioru na dalsze poszukiwania
Krok 8: ipis  + 1 ; v > T[is] → druga połówka
Krok 9: Idź do kroku 2  
Krok 10: ik  ← is  - 1 ; v < T[is] → pierwsza połówka
Krok 11: Idź do kroku 2  

 

Przykładowe dane dla programu:

Pierwsza liczba v  określa poszukiwaną wartość. Druga liczba n  określa ilość elementów w zbiorze. Następne n  liczb definiuje n  kolejnych elementów. Liczby zbioru są całkowite.

 

307
210
0 3 5 7 9 11 13 13 14 15 17 19 22 24 26
27 30 32 33 36 38 41 42 44 46 49 50 53 53 54
56 58 61 63 63 66 69 72 75 78 78 80 81 82 85
85 86 88 89 89 90 93 95 96 96 97 97 98 101 102
103 105 106 107 109 111 112 114 115 116 119 119 119 120 121
124 127 129 131 131 134 137 137 140 140 141 144 146 146 147
149 150 151 154 156 159 160 161 164 166 166 167 169 172 174
174 174 175 176 179 180 181 182 184 185 185 187 189 190 190
192 195 196 197 197 200 200 202 202 204 205 208 208 210 210
210 212 212 212 213 215 215 215 218 221 223 223 226 227 229
231 232 234 234 234 234 236 239 242 243 245 248 248 249 249
250 252 254 257 257 258 258 260 261 262 262 262 264 266 268
269 271 273 273 273 273 276 278 280 282 282 285 286 286 288
288 290 292 295 298 301 303 304 307 308 309 309 311 312 315

 

Program wyszukiwania binarnego

 

// Wyszukiwanie binarne
// (C)2010 I LO w Tarnowie
//------------------------

#include <iostream>

using namespace std;

int main()
{
    int * T,v,n,i,p,ip,ik,is;

    // odczytujemy poszukiwaną wartość

    cin >> v;

    // odczytujemy liczbę elementów

    cin >> n;

    // tworzymy tablicę dynamiczną o n elementach

    T = new int[n];

    // wczytujemy elementy do tablicy

    for(i = 0; i < n; i++) cin >> T[i];

    // szukamy elementu o wartości v

    p = -1;
    ip = 0; ik = n - 1;

    while(ip <= ik)
    {
        is = (ip + ik) / 2;

        if(v == T[is])
        {
            p = is;
            break;
        }

        if(v < T[is]) ik = is - 1;
        else          ip = is + 1;
    }

    // wyświetlamy wyniki

    cout << endl;

    for(i = 0; i < n; i++)
        if(i == p) cout << "*" << T[i] << "* ";
        else       cout << T[i] << " ";

    cout << endl << endl;

    if(p >= 0) cout << "Element " << v << " na pozycji " << p << endl;
    else       cout << "Elementu " << v << " nie ma w zbiorze\n";

    // usuwamy tablicę dynamiczną

    delete [] T;

    return 0;
}

 

Zmodyfikuj program, tak aby liczył liczbę obiegów pętli algorytmu wyszukiwania binarnego. Wyciągnij wnioski z wyników.

 


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

©2024 mgr Jerzy Wałaszek

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

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

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe