Login lub e-mail Hasło   

Algorytmy wyszukujące - wyszukiwanie binarne

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/al(...)ex.html
Jeśli zbiór jest posortowany (np. rosnąco) , to problem wyszukiwania elementu da się rozwiązać znacznie efektywniej stosując poniższą metodę zwaną wyszukiwaniem binarny...
Wyświetlenia: 18.043 Zamieszczono 03/11/2006

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

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ń. Wnioski wyciąg sam.

   
   
   

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


Zwróć 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 + i  
 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:

d1 d2 d3 ... dsr-1 dsr dsr+1 ... dn-1 dn

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:

ip > ik

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

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
krok 1: ip 1;  ik n;  p 0
krok 2: Dopóki ip ik: wykonuj kroki 3...5
krok 3:
    isr =     ip + i  
 2 
krok 4:     Jeśli w = d[isr], to p isr i zakończ algorytm
krok 5:     Jeśli w > d[isr], to ip isr + 1.  Inaczej ik isr - 1
krok 6: Zakończ algorytm

Na początku pracy algorytmu ustawiamy zmienne robocze. Zmienna ip przechowuje pierwszy element partycji, w której wykonujemy oszukiwanie elementu w. Zmienne ik przechowuje ostatni indeks elementu w tej partycji. Początkowo partycja obejmuje cały zbiór.

W zmiennej p algorytm umieści indeks elementu zbioru równego poszukiwanemu elementowi. Wstępnie ustawiamy ten indeks na 0 w celu zaznaczenia, iż element nie został jeszcze znaleziony.

Rozpoczynamy pętlę warunkową. Warunkiem kontynuacji jest niepusta partycja, w której poszukuje się elementu w. Pierwszą czynnością w pętli jest wyliczenie indeksu elementu środkowego isr. Następnie sprawdzamy, czy element poszukiwany jest równy elementowi środkowemu. Jeśli tak, to w zmiennej p umieszczamy indeks elementu środkowego i algorytm kończymy.

W przeciwnym razie poszukiwany element w może leżeć w lewej partycji jeśli jest mniejszy od elementu środkowego lub w prawej partycji w przypadku przeciwnym. Ustawiamy zatem odpowiednio zmienne ip oraz ik:

w > d[isr] - prawa partycja, ip przesuwamy na is + 1, ik pozostaje bez zmian
w d[isr] - lewa partycja, ip pozostaje bez zmian, ik przesuwamy na isr - 1.

Po tej operacji wracamy na początek pętli.

Gdy pętla warunkowa się zakończy w sposób naturalny (w wyniku ostatniego podziału otrzymujemy pustą partycję), zmienna p zawiera 0. Oznacza to, iż element w nie występuje w zbiorze. Jest to przypadek pesymistyczny i wymaga wykonania log2n + 1 obiegów pętli.


   
   
   

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

 
       

Program generuje pseudolosowy zbiór uporządkowany o 100 elementach z zakresu od 0 do 99. Następnie wybiera losowo wartość z tego samego zakresu i poszukuje jej w zbiorze za pomocą algorytmu wyszukiwania binarnego.

Efekt uruchomienia programu
   Wyszukiwanie binarne
--------------------------
(C)2006 mgr Jerzy Wałaszek

0 1 2 3 4 5 5 5 6 7 7 8 9 9 10 10 11 12 12 12
13 16 18 20 23 24 24 25 26 26 29 30 30 32 33 33 34 34 37 38
38 41 44 45 49 50 50 53 54 54 55 57 58 58 59 59 60 61 61 63
63 65 66 67 67 68 68 69 72 (73) 74 74 75 75 75 75 76 76 76 76
77 77 77 79 79 80 83 83 85 85 86 88 89 90 90 90 95 95 95 97


Element w = 73 jest na pozycji nr 70

KONIEC. Naciśnij dowolny klawisz...

//    Wyszukiwanie binarne
//----------------------------
// (C)2006 mgr Jerzy Wałaszek
// I LO w Tarnowie
//----------------------------

program binsearch;

{$APPTYPE CONSOLE}

const

N = 100; // Liczba elementów w zbiorze
M = 99; // Maksymalna wartość elementu

var
d : array[1..N] of integer;
w,i,ip,ik,isr,p : integer;

begin
writeln(' Wyszukiwanie binarne ');
writeln('--------------------------');
writeln('(C)2006 mgr Jerzy Walaszek');
writeln;

// Generujemy zbiór pseudolosowy

randomize;
for i := 1 to N do d[i] := random(M + 1);

// Zbiór sortujemy rosnąco

for i := N - 1 downto 1 do
begin

w := d[i]; ip := i + 1;
while (ip <= N) and (w > d[ip]) do
begin

d[ip - 1] := d[ip]; inc(ip);
end;
d[ip - 1] := w;
end;

// Generujemy poszukiwany element

w := random(M + 1);

// Szukamy elementu w

ip := 1; ik := N; p := 0;
while ip <= ik do
begin

isr := (ip + ik) div 2;
if w = d[isr] then
begin

p := isr; break;
end
else if
w > d[isr] then
ip := isr + 1
else
ik := isr - 1;
end;

// Prezentujemy wyniki

for i := 1 to N do
if
i = p then write('(',d[i]:2,')') else write(d[i]:3,' ');
writeln; writeln;
write('Element w = ',w);
if p > 0 then
writeln(' jest na pozycji nr ',p)
else
writeln(' w zbiorze nie wystepuje.');
writeln;

// Gotowe

writeln('Nacisnij klawisz Enter...');
readln;
end.
//    Wyszukiwanie binarne
//----------------------------
// (C)2006 mgr Jerzy Wałaszek
// I LO w Tarnowie
//----------------------------

#include <iostream>
#include <iomanip>

using namespace std;

const int N = 100; // Liczba elementów w zbiorze
const int M = 99; // Maksymalna wartość elementu

int main(void)
{
int d[N + 1],w,i,ip,ik,isr,p;

cout << " Wyszukiwanie binarne \n"
"--------------------------\n"
"(C)2006 mgr Jerzy Walaszek\n\n"
;

// Generujemy zbiór pseudolosowy

srand((unsigned)time(NULL));
for(i = 1;i <= N; i++) d[i] = rand() % (M + 1);

// Zbiór sortujemy rosnąco

for(i = N - 1; i >= 1; i--)
{
w = d[i]; ip = i + 1;
while((ip <= N) && (w > d[ip]))
{
d[ip - 1] = d[ip]; ip++;
}
d[ip - 1] = w;
}

// Generujemy poszukiwany element

w = rand() % (M + 1);

// Szukamy elementu w

ip = 1; ik = N; p = 0;
while(ip <= ik)
{
isr = (ip + ik) / 2;
if(w == d[isr])
{
p = isr; break;
}
else if(w > d[isr])
ip = isr + 1;
else
ik = isr - 1;
}

// Prezentujemy wyniki

for(i = 1; i <= N; i++)
if(i == p)
cout << "(" << setw(2) << d[i] << ")";
else
cout << setw(3) << d[i] << " ";
cout << "\nElement w = " << w;
if(p)
cout << " jest na pozycji nr " << p << endl;
else
cout << " w zbiorze nie wystepuje.\n";
cout << endl;

// Gotowe

system("pause"); return 0;
}
'    Wyszukiwanie binarne
'----------------------------
' (C)2006 mgr Jerzy Wałaszek
' I LO w Tarnowie
'----------------------------

Module Module1

Sub Main()
Const N = 100 ' Liczba elementów w zbiorze
Const M = 99 ' Maksymalna wartość elementu

Dim d(N), w, i, ip, ik, isr, p As Integer

Console.WriteLine(" Wyszukiwanie binarne ")
Console.WriteLine("--------------------------")
Console.WriteLine("(C)2006 mgr Jerzy Wałaszek")
Console.WriteLine()

' Generujemy zbiór pseudolosowy

Randomize()
For i = 1 To N : d(i) = Int(Rnd(1) * (M + 1)) : Next

' Zbiór sortujemy rosnąco

For i = N - 1 To 1 Step -1
w = d(i) : ip = i + 1
While (ip <= N) AndAlso (w > d(ip))
d(ip - 1) = d(ip) : ip += 1
End While
d(ip - 1) = w
Next

' Generujemy poszukiwany element

w = Int(Rnd(1) * (M + 1))

' Szukamy elementu w

ip = 1 : ik = N : p = 0
While ip <= ik
isr = (ip + ik) \ 2
If w = d(isr) Then
p = isr : Exit While
ElseIf w > d(isr) Then
ip = isr + 1
Else
ik = isr - 1
End If
End While

' Prezentujemy wyniki

For i = 1 To N
If i = p Then
Console.Write("({0,2})", d(i))
Else
Console.Write(" {0,2} ", d(i))
End If
Next

Console.WriteLine()
Console.WriteLine()
Console.Write("Element w = {0}", w)
If p > 0 Then
Console.WriteLine(" jest na pozycji nr {0}", p)
Else
Console.WriteLine(" w zbiorze nie występuje.")
End If

' Gotowe

Console.WriteLine()
Console.WriteLine("KONIEC. Naciśnij dowolny klawisz...")
Console.ReadLine()

End Sub

End Module
 
# -*- coding: cp1250 -*-
# Wyszukiwanie binarne
#----------------------------
# (C)2006 mgr Jerzy Wałaszek
# I LO w Tarnowie
#----------------------------

import random

N = 100 # Liczba elementów w zbiorze
M = 99 # Maksymalna wartość elementu

d = []

print " Wyszukiwanie binarne "
print "--------------------------"
print "(C)2006 mgr Jerzy Walaszek"
print

# Generujemy zbiór pseudolosowy

for i in range(N): d.append(random.randint(0, M))

# Zbiór sortujemy rosnąco

d.sort()

# Generujemy poszukiwany element

w = random.randint(0, M)

# Szukamy elementu w

ip, ik, p = 0, N - 1, -1
while ip <= ik:
isr = (ip + ik) / 2
if w == d[isr]:
p = isr; break
elif w > d[isr]:
ip = isr + 1
else:
ik = isr - 1

# Prezentujemy wyniki

for i in range(N):
if i == p:
print "(%2d)" % d[i],
else:
print " %2d " % d[i],
print
print

print "Element w =", w,
if p >= 0:
print "jest na pozycji nr", p + 1
else:
print "w zbiorze nie wystepuje."
print

# Gotowe

raw_input("Nacisnij klawisz Enter...")
<html>
<head>
</head>
<body>
<div align=
"center">
<form style="BORDER-RIGHT: #ff9933 1px outset; PADDING-RIGHT: 4px;
BORDER-TOP: #ff9933 1px outset; PADDING-LEFT: 4px;
PADDING-BOTTOM: 1px; BORDER-LEFT: #ff9933 1px outset;
PADDING-TOP: 1px; BORDER-BOTTOM: #ff9933 1px outset;
BACKGROUND-COLOR: #ffcc66"
name="frmBinSearch">
<h4 id=
"out_t0" style="text-align: center">Wyszukiwanie binarne</h4>
<p style=
"TEXT-ALIGN: center">
(C)2006 mgr Jerzy Wałaszek<br>
I LO w Tarnowie
</p>
<hr>
<p style=
"TEXT-ALIGN: center">
<input type=
"button" value="Szukaj" name="B1" onclick="main();">
</p>
<p style=
"TEXT-ALIGN: center" id="t_out">...</p>
</form>

<script language=
javascript>

// Wyszukiwanie binarne
//----------------------------
// (C)2006 mgr Jerzy Wałaszek
// I LO w Tarnowie
//----------------------------

function main()
{
var N = 100; // Liczba elementów w zbiorze
var M = 99; // Maksymalna wartość elementu
var d = new Array(N + 1);
var w,i,ip,ik,isr,p,l,t;

// Generujemy zbiór pseudolosowy

for(i = 1; i <= N; i++) d[i] = Math.floor(Math.random() * (M + 1));

// Zbiór sortujemy rosnąco

for(i = N - 1; i >= 1; i--)
{
w = d[i]; ip = i + 1;
while((ip <= N) && (w > d[ip]))
{
d[ip - 1] = d[ip]; ip++;
}
d[ip - 1] = w;
}

// Generujemy poszukiwany element

w = Math.floor(Math.random() * (M + 1));

// Szukamy elementu w

ip = 1; ik = N; p = l = 0;
while(ip <= ik)
{
isr = Math.floor((ip + ik) / 2);
l++;
if(w == d[isr])
{
p = isr; break;
}
else if(w > d[isr])
ip = isr + 1;
else
ik = isr - 1;
}

// Prezentujemy wyniki

t = "";
for(i = 1; i <= N; i++)
if(i == p)
t += " <b><font color=red>(" + d[i] + ")</font></b>";
else
t += " &nbsp;" + d[i] + "&nbsp;";
t += "<br><br>Ilość prób = " + l + "<br><br>Element w = " + w;
if(p > 0)
t += " jest na pozycji nr " + p;
else
t += " w zbiorze nie wystepuje";

// Gotowe

document.getElementById("t_out").innerHTML = t;
}

</script>

</div>
</body>
</html>
Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Podobne artykuły


7
komentarze: 1 | wyświetlenia: 6261
16
komentarze: 5 | wyświetlenia: 9003
9
komentarze: 0 | wyświetlenia: 2782
49
komentarze: 18 | wyświetlenia: 64971
12
komentarze: 3 | wyświetlenia: 29778
37
komentarze: 9 | wyświetlenia: 28513
11
komentarze: 2 | wyświetlenia: 33149
18
komentarze: 11 | wyświetlenia: 9266
7
komentarze: 1 | wyświetlenia: 34647
17
komentarze: 4 | wyświetlenia: 14162
15
komentarze: 5 | wyświetlenia: 32758
13
komentarze: 2 | wyświetlenia: 22958
12
komentarze: 2 | wyświetlenia: 18504
11
komentarze: 1 | wyświetlenia: 86398
 
Autor
Artykuł




Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska