obrazek

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

obrazek

Wyszukiwanie binarne

Zbiór uporządkowany (ang. ordered set) to taki, w którym elementy występują w określonym porządku, czyli kolejności. Jeśli elementy są liczbami (a większość zbiorów da się sprowadzić do liczb), to porządek może być:

rosnący - każdy następny element zbioru jest większy od swojego poprzednika. W zbiorze nie ma elementów równych. Taki porządek nazywamy porządkiem mocnym.
Np. {0 2 4 7 12 13 16 74 125 200 333 ...}
malejący - każdy następny element jest mniejszy od swojego poprzednika. W zbiorze nie ma elementów równych - porządek mocny.
Np. (100 96 64 32 15 10 8 4 2 -4 -9 -22 ... }
niemalejący - każdy następny element jest równy lub większy od swojego poprzednika. Elementy o tych samych wartościach mogą występować wielokrotnie obok siebie. Taki porządek nazywamy porządkiem słabym.
Np. { 1 1 1 1 1 3 4 4 5 8 12 12 12 33 40 ... }
nierosnący - każdy następny element jest równy lub mniejszy od swojego poprzednika. Elementy o tych samych wartościach mogą się powtarzać - porządek słaby.
Np. {100 95 75 75 75 40 23 12 12 12 12 7 6 4 2 2 2 1 1 1 ... }

Wykorzystując fakt uporządkowania zbioru można znacznie przyspieszyć wyszukiwanie danych. Zasada nazywa się wyszukiwaniem binarnym (ang. binary search) i jest następująca (dla porządku rosnącego):

Ze zbioru bierzemy element środkowy i porównujemy go z poszukiwaną wartością. Jeśli jest zgodność, to zwracamy pozycję znalezionego elementu i kończymy. Jeśli nie ma zgodności, to na podstawie wyniku porównania za nowy zbiór przyjmujemy jedną z połówek:

lewą, jeśli poszukiwana wartość była mniejsza od elementu środkowego, gdyż tam może występować
prawą, jeśli poszukiwana wartość była większa od elementu środkowego - ten sam powód co powyżej.

Całą procedurę powtarzamy aż do momentu znalezienia elementu lub do osiągnięcia zbioru pustego.

Zwróć uwagę, iż po każdym porównaniu liczebność zbioru do przeszukania spada dwukrotnie. Porównań w najgorszym razie wykonamy tyle, ile otrzymamy kolejnych połówek zbioru. Załóżmy, iż zbiór liczy 100 elementów. Wtedy:

Numer porównania	Liczebność kolejnej połówki zbioru
1	50
2	25
3	12
4	6
5	3
6	1
7	0 - koniec

Jak widzisz, już po wykonaniu 6 porównań można stwierdzić, że poszukiwanego elementu w zbiorze 100 elementowym nie ma. W przypadku wyszukiwania liniowego odpowiedź otrzymalibyśmy dopiero po 100 porównaniach. W przypadku bardziej licznych zbiorów wynik jest jeszcze korzystniejszy. Np. dla zbioru zawierającego 4 miliardy elementów wystarczy wykonać maksymalnie 32 porównania. Jeśli problem rozważysz dokładniej, co proponujemy bardziej uzdolnionym uczniom, to dojdziesz do wniosku, iż liczba porównań L_n dla n elementowego zbioru uporządkowanego jest równa tyle, ile wynosi wykładnik największej potęgi liczby 2 niewiększej od n plus 1. Matematycznie zapisujemy to tak:

L_n = log₂(n) + 1

We wzorze pojawia się logarytm dwójkowy z n. Pojęcie logarytmów jest bezpośrednio związane z potęgowaniem.

Zapamiętaj:

Logarytm przy podstawie a z liczby x jest wykładnikiem potęgowym b, do którego należy podnieść podstawę a, aby otrzymać x:

log_ax = b wtedy i tylko wtedy, gdy a^b = x

W logarytmie dwójkowym podstawa jest równa 2. Zatem logarytmem dwójkowym z x jest taki wykładnik potęgowy b, iż 2 podniesione do potęgi b daje x:

log₂x = b, 2^b = x

Przykłady.

Mamy obliczyć logarytm dwójkowy z liczby 8. Musimy znaleźć takie b, aby:

2^b = 8

Oczywiście:

2³ = 8, zatem b = 3. To b jest właśnie logarytmem dwójkowym z 8, co zapisujemy następująco:

log₂8 = 3, bo 2³ = 8

log₂16 = 4, bo 2⁴ = 16
log₂128 = 7, bo 2⁷ = 128

Ponieważ porównania są w naszym algorytmie operacjami dominującymi i od ich liczby zależy czas wykonywania algorytmu, to jego klasa złożoności obliczeniowej wynosi O(log n) i nosi nazwę złożoności logarytmicznej. To bardzo korzystna własność.

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 poszukiwana wartość v < 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 v > 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
v	-	wartość poszukiwanego elementu

Wyjście:

indeks elementu o wartości v lub -1, jeśli nie odnaleziono elementu o wartości v.

Zmienne pomocnicze

i_sr

indeks elementu środkowego. i_sr∈C

Lista kroków:

K01:

Dopóki i_p ≤ i_k wykonuj K02...K07

; w pętli poszukujemy elementu o wartości v

K02:

i_sr =		i_p + i_k
		2

; wyznaczamy indeks elementu środkowego

K03:

Jeśli v = Z[i_sr], to zakończ zwracając i_sr

K04:

Jeśli v < Z[i_sr], to i_p ← i_sr + 1
inaczej i_k ← i_sr - 1

; wybieramy odpowiednią połówkę zbioru na dalsze poszukiwania

K05:

Zakończ zwracając -1

Program:

Ćwiczenie na lekcji

Ćwiczenia

Porównaj algorytm wyszukiwania binarnego z algorytmem bisekcji. Czy widzisz jakieś podobieństwa?

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