Binsearch.pdf

(52 KB) Pobierz
Binsearch.dvi
Binarysearch-wyszukiwaniebinarne
MateuszBaranowski(baranina@gmail.com)
25stycznia2009
DEFINICJA: Wyszukiwanie binarne jest metod¡ pozwalaj¡c¡ na znalezienie po»¡danego elementu w posortowanej
tablicy w czasie (log 2 n ).
Okazuje si¦, »e w praktyce posiada o wiele szersze zastosowanie.
Problem wyszukiwania binarnego mo»na sprowadzi¢ do nast¦puj¡cej postaci. Mamy pewien przedział [ a,b ], wiemy, »e
je»eli pewien element posiada dan¡ własno±¢ (lub inaczej spełnia pewien warunek), to wszystkie elementy ”wi¦ksze” od
niego te» musz¡ spełnia¢ ten warunek. Je»eli natomiast dany element nie spełnia danego warunku, to wszystkie elementy
”mniejsze”odniegote»niemog¡spełnia¢tegowarunku.Słowa”wi¦ksze”i”mniejsze”wtymprzypadkuoznaczaj¡przyj¦ty
przez nas porz¡dek, czyli kolejno±¢, st¡d cudzysłów. W tak zdefiniowanym przedziale chcemy znale¹¢ najmniejszy element
w , nale»¡cy do danego przedziały, który spełnia dan¡ własno±¢.
Taki przedział mo»emy zilustrowa¢ nast¦puj¡co:
a
w
b
nie spełnia
spełnia
Najbardziejintuicyjnym, cho¢ do±¢ nieoptymalnympodej±ciem do wyszukiwaniaelementu w byłobysprawdzaniekolej-
nychelementównale»¡cychdo przedziałuzaczynaj¡codjednegoz ko«ców,aczkolwiekw najgorszymmo»liwymprzypadku
oznaczałoby to przejrzenie całej tablicy, czyli zło»ono±¢ liniow¡ ( O ( n )).
Wyszukuj¡c binarnie nie staramy si¦ jednoznacznie okre±li¢ danego elementu, lecz raczej ”obcina¢” przedział [ a,b ], a»
przedziałtenb¦dzienatylemały,»eka»dyelement,którysi¦wnimznajdujeb¦dzie”zadowalaj¡cy”.Wprzypadkuszukania
konkretnego elementu w tablicy oznacza to wielko±¢ przedziału równ¡ 0, czyli a = b .
Obcinanie przedziału polega na powtarzaniu nast¦puj¡cych operacji:
1. Je»eli przedział jest dostatecznie mały ko«czymy wyszukiwanie, naszym wynikiem jest a , b¡d¹ b , w przeciwnym
przypadku przechodzimy do punktu 2 .
2. Wyznaczamyelement±rodkowy c równy a + 2 (lub a + b +1
2 wprzypadku,gdywoperujemynaliczbachcałkowitychprzy
”obcinaniu” lewej cz¦±ci przedziału nie ”obcinamy” elementu bie»¡cego).
3. W zale»no±ci od własno±ci elementu c ”obcinamy” przedział:
• Je»eli c nie spełnia danego warunku, to niech a := c (w przypadku całkowitoliczbowych a := c +1), poniewa»
wiemy, »e wszystkie elementy ”mniejsze” od c nie spełniaj¡ warunku.
• Je»eli c spełnia warunek, to niech b := c (tak samo w przypadku całkowitoliczbowych, bo element c mo»e by¢
minimalnymspełniaj¡cymdan¡własno±¢),poniewa»wszystkie”wi¦ksze”elementycoprawdaspełniaj¡warunek,
ale na pewno s¡ wi¦ksze od c , zatem nie ma sensu ich sprawdza¢.
• Dla niektórych przeszukiwa«istnieje jeszcze jedna mo»liwo±¢.Je»eli jeste±my w stanie jednoznacznie stwierdzi¢,
»e c jestnajmniejszymelementemspełniaj¡cymdan¡własno±¢,to a := c i b := c ,poniewa»niemasensuzaw¦»a¢
przedziału skoro ten element nas zadowala.Wyznaczamy go zatem jednoznacznie.
Przechodzimy do punktu 1 .
1
216249381.001.png
Abstrakcja
Dla przykładowegoprzedziału przeszukiwanie mo»e wygl¡da¢ nast¦puj¡co:
Wyznaczamy element ±rodkowy c :
a
c
b
nie spełnia
spełnia
c nie spełnia własno±ci, zatem a := c :
a
b
Przedział [ a,b ] jest za du»y ,zatem ponownie wyznaczamy c = a + b
2 :
a
c
b
Element c spełnia własno±¢, wi¦c b := c :
a b
Przedział [ a,b ] jest za du»y ,zatem ponownie wyznaczamy c = a + b
2 :
a b
c
Element c spełnia własno±¢, wi¦c b := c :
a b
Przedział [ a,b ] jest za du»y ,zatem ponownie wyznaczamy c = a + b
2 :
a b
c
Element c nie spełnia własno±ci, wi¦c a := c :
a b
Jak łatwo zauwa»y¢ przedział [ a,b ] za ka»dym ”obci¦ciem” zmniejsza si¦ dwukrotnie. W ten sposób zdecydowan¡
wi¦kszo±¢ elementów odrzucamy z puli zanim je sprawdzimy, przez co rozwi¡zanie to działa znacznie szybciej ni» nasze
rozwi¡zanie intuicyjne.
Dlaprzypomnienialog 2 18446744073709551616=64,czyliprzeszykuj¡cpokoleiwnajgorszymprzypadkub¦dziemymusieli
sprawdzi¢ 18446744073709551616elementów, natomiast w przeszukiwaniu binarnym tylko ok. 64.
2
216249381.002.png 216249381.003.png 216249381.004.png
Przykład
Problem:
Mamy dane tablic¦ t:array of longint; wypełnion¡ posortowanymi rosn¡co n liczbami całkowitymi. Naszym zadaniem jest
maj¡c dane liczb¦ x znale¹¢ najmniejsz¡ liczb¦ nie mniejsz¡ ni» x w tablicy t.
Rozwi¡zanie:
Function BinarySearch(x,n:longint;t:arrayoflongint):longint;
var
a,b,c:longint;
Begin
a:=0;
b:=n-1; //sizeof dajerozmiartablicywbajtach, alongintto4bajty
while a < b do //dopóki przedziałniejestjednoelementowy
begin
c:=(a+b)div2; //±rodek przedziału
ift[c] > xthenb:=celse //je»eli jestwi¦kszytoodcinamy zprawejstrony
ift[c] < xthena:=c+1else //mniejszy, wi¦codcinamyzlewejstrony”+1”,bocte»niepasuje
begin
a:=c; //t[c]=x,wi¦ccjestelementemwła±ciwym
b:=c; //zatemzarównowybieramy przedział jednoelementowy
end;
end;
BinarySearch:=t[a];
End;
Powy»sza funkcja Pokazuje jedno z mo»liwych zastosowa« wyszukiwania binarnego. W szeroko poj¦tej algorytmice
metodatajestcz¦stou»ywanapodczasoptymalizacjiszerokiejgamyprocesówobliczeniowych(np.aproksymacyjnych).Dla
lepszego zrozumienia radz¦ prze±ledzi¢ sposób w jaki zmieniaj¡ si¦ dane dla kilku wi¦kszych przykładów (np. 20 i wi¦cej
liczb). Je»eli »¡dany element nie istnieje zwracany jest najwi¦kszy element w tablicy.
3

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin