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ć:

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:

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ń Ln 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:

 

Ln = log2(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:

logax = b wtedy i tylko wtedy, gdy ab = 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:

log2x = b, 2b = x

 

Przykłady.

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

2b = 8

Oczywiście:

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

log28 = 3, bo 23 = 8

log216 = 4, bo 24 = 16
log2128 = 7, bo 27 = 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:

 

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 poszukiwana wartość v < 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 v > 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[ ], ipC
ik  - indeks ostatniego elementu w tablicy Z[ ], ikC
Z[ ]  - tablica do wyszukania elementu. Indeksy od ip do ik
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
isr  -  indeks elementu środkowego. isrC
Lista kroków:
K01: Dopóki ipik wykonuj K02...K07 ; w pętli poszukujemy elementu o wartości v
K02:
    isr =   ip + ik  
2
; wyznaczamy indeks elementu środkowego
K03:     Jeśli v = Z[isr], to zakończ zwracając  isr  
K04:     Jeśli v < Z[isr], to ipisr + 1
    inaczej                ikisr - 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?

 



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.