Projekt

Algorytmy i struktury danych

Temat: Wyszukiwanie binarne

Prowadzący: Wykonawcy:

dr inż. Krzysztof Pancerz Kopanska Halyna 46799

Yatsenyuk Taras 46836

Rzeszów, 2012 r.

Spis treści

1. Co to takie – „Wyszukiwanie binarne?”..........................................................3

2. Cel projektu.....................................................................................................4

3. Jak pracujązasady wyszukiwania binarnego. Algorytm...................................4

4. Specyfikacja problemu:...................................................................................6

• Dane wejściowe..................................................................6

• Dane wyjściowe..................................................................6

• Zmienne pomocnicze..........................................................6

5. Lista kroków.....................................................................................................7

6. Opisanieprogramu...........................................................................................7

7. Program w języku C++......................................................................................8

8. Testowanie algorytmu (czas wykonania dla duzych(1000 elementów) i małych (20 elementów) tablic na różnych maszynach). Wnioski................................10

9. Streszczenie pracy...........................................................................................14

10. Bibliografia.......................................................................................................15

C

Wyszukiwanie binarne -

(z angielskiego binary search), algorytm wyszukiwania informacji w uporządkowanym ciągu elementów, polegający na połowieniu ciągu i odnoszeniu kolejnego kroku do tej połowy, w której można oczekiwać występowania poszukiwanego elementu. Intuicyjną metodę wyszukiwania (nazywaną interpolacyjną), zbliżoną do ścisłego wyszukiwania biernego, stosuje każda każdy Czytelnik przy korzystaniu z tego słownika, otwierając go zrazu w dowolnym miejscu i zaglądając na lewo lub na prawo w zależności od napotkanego wyrazu.

o to takie – „Wyszukiwanie binarne?”

Cel projektu:

Opisanie, emplementacja i testowanie algorytmu wyszukiwania binarnego.

Jak pracują zasady wyszukiwania binarnego.

Algorytm

Jeśli zbiór jest posortowany (np. rosnąco), to problem wyszukiwania elementu da się rozwiązać znacznie efektywniej stosując naszą metodę wyszukiwania binarnego:

Jeśli zbiór jest pusty, to kończymy algorytm z wynikiem negatywnym. W przeciwnym razie wyznaczamy element leżący w środku zbioru. Porównujemy poszukiwany element z elementem środkowym. Jeśli są sobie równe, to zadanie wyszukania elementu jest wypełnione i kończymy algorytm. W przeciwnym razie element środkowy dzieli zbiór na dwie partycje - lewą z elementami mniejszymi od środkowego oraz prawą z elementami większymi. Jeśli porównywany element jest mniejszy od środkowego elementu zbioru, to za nowy zbiór poszukiwań przyjmujemy lewą partycję. W przeciwnym razie za nowy zbiór przyjmujemy prawą partycję. W obu przypadkach rozpoczynamy poszukiwania od początku, ale w nowo wyznaczonym zbiorze.

Dla zobrazowania algorytmu wyszukiwania binarnego znajdziemy element 2 w zbiorze:

{ 1 1 2 4 4 5 6 6 6 7 7 8 8 9 9 }

Lp.	Operacja	Opis
1.	1 1 2 4 4 5 6 6 6 7 7 8 8 9 9	Znajdujemy środkowy element zbioru.
2.	>>>>>>> 2 1 1 2 4 4 5 6 6 6 7 7 8 8 9 9	Element środkowy porównujemy z poszukiwanym elementem. Nie ma równości. Za nowy zbiór poszukiwań wybieramy lewą partycję.
3.	1 1 2 4 4 5 6 6 6 7 7 8 8 9 9	Znajdujemy środkowy element zbioru.
4.	>>> 2 1 1 2 4 4 5 6 6 6 7 7 8 8 9 9	Element środkowy porównujemy z poszukiwanym. Znów nie ma równości. Wybieramy lewą partycję.
5.	1 1 2 4 4 5 6 6 6 7 7 8 8 9 9	Znajdujemy element środkowy.
6.	2 > 1 1 2 4 4 5 6 6 6 7 7 8 8 9 9	Porównujemy element środkowy z poszukiwanym. Brak równości. Wybieramy prawą partycję - należy do niej tylko jeden element.
7.	1 1 2 4 4 5 6 6 6 7 7 8 8 9 9	Znajdujemy element środkowy.
8.	2 1 1 2 4 4 5 6 6 6 7 7 8 8 9 9	Porównujemy elementy - jest zgodność. Poszukiwany element został znaleziony w zborze.

Każde porównanie sprowadza nam problem do zbioru o połowę mniejszego. W najgorszym przypadku wykonamy log2n + 1 porównań. Zatem przedstawiony sposób wyszukiwania elementu zbioru posiada logarytmiczną klasę złożoności obliczeniowej O(log n). Czy to dużo, czy mało? Bardzo mało, logarytm rośnie wolno. Na przykład w zbiorze zawierającym 1.000.000.000 elementów algorytm wyszukiwania binarnego wykona maksymalnie 30 porównań, podczas gdy algorytm wyszukiwania liniowego będzie średnio musiał wykonać 500.000.000 porównań.

Gdyby w punkcie 8 powyższego przykładu porównanie dało wynik negatywny, to jednoelementowego zbioru nie można już podzielić na dalsze partycje. Innymi słowy otrzymalibyśmy partycje puste. Zatem zgodnie z opisem algorytmu skończylibyśmy jego wykonanie z wynikiem negatywnym - poszukiwanego elementu nie byłoby w zbiorze

N ależy zwrócić uwagę, iż algorytm wyszukiwania binarnego nie gwarantuje znalezienia pierwszego wystąpienia elementu w zbiorze, jeśli element poszukiwany występuje w nim kilkakrotnie.

Pozostaje wyjaśnienie wyznaczenia elementu środkowego oraz podziału na partycje. Otóż załóżmy, iż zmienna ip zawiera początkowy indeks elementu w partycji, a ik zawiera odpowiednio indeks końcowy. Na początku pracy algorytmu ip ustawiamy na 1, a ik na n. W ten sposób obejmiemy cały zbiór.

d1	d2	d3	...	dn-1	dn
ip					ik

Element środkowy wyznaczamy jako całkowitą średnią arytmetyczną indeksów pierwszego i ostatniego elementu w tablicy:

isr =		ip + ik
		2

d1	d2	d3	...	dsr-1	dsr	dsr+1	...	dn-1	dn
ip					isr				ik

Jeśli zbiór jest uporządkowany, to jego elementy spełniają warunek:

d₁   d₂   d₃   ...   d_sr-1   d_sr   d_sr+1   ...   d_n-1   d_n

W lewej partycji są wszystkie elementy o wartościach nie większych od elementu środkowego dsr. Lewa partycja obejmuje zatem elementy o indeksach od ip do is - 1.

W prawej partycji są wszystkie elementy o wartościach nie mniejszych od elementu środkowego dsr. Prawa partycja obejmuje elementy o indeksach od isr + 1 do ik.

Umówmy się, iż partycja będzie pusta, gdy indeks jej początku jest większy od indeksu końca:

i_p > i_k

Tak określona partycja nie może zawierać żadnego elementu.

Specyfikacja problemu

Dane wejściowe

N	- ilość elementów w przeszukiwanym zbiorze.  n   N
d[ ]	- posortowany rosnąco zbiór danych. Indeksy elementów rozpoczynają się od 1.
W	- wartość poszukiwanego elementu. Typ elementu taki sam jak typ elementów zbioru.

Dane wyjściowe

P - pozycja elementu w zbiorze, p   C,   1   p   n - element znaleziony,   p = 0 - element nie znaleziony

Zmienne pomocnicze

ip	- zawiera indeks pierwszego elementu w partycji. ip   C
ik	- zawiera indeks ostatniego elementu w partycji, ik   C
isr	- zawiera indeks środkowego elementu, isr   C