Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

©2010 mgr Jerzy Wałaszek I LO w Tarnowie

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 e_s. Jeśli v = e_s, 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 < e_s - 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 e_s.

2. v > e_s - 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:

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

Indeksy i_p  i i_k  określają obszar zbioru w tablicy T[ ]. 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_s:

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

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

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

Algorytm wyszukiwania binarnego

Wejście

Wyjście:

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

Zmienne pomocnicze

Lista kroków:

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