Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek, wersja1.0 |
©2010 mgr
Jerzy Wałaszek |
Materiały pomocnicze:
Tablice i podstawowe operacje
na tablicach
Wskaźniki i tablice dynamiczne
Przeszukiwanie liniowe oraz liniowe z
wartownikiem
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:
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.
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.
ip | - | indeks pierwszego elementu w tablicy T[ ], ip ∈C |
ik | - | indeks ostatniego elementu w tablicy T[ ], ik ∈C |
T[ ] | - | tablica do wyszukania elementu. Indeksy od ip do ik |
v | - | wartość poszukiwanego elementu |
p = indeks elementu o wartości v
p = -1, jeśli nie odnalezienia elementu o wartości v
is | - | indeks elementu środkowego. is∈C |
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: |
|
; 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: | ip ← is + 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 |
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