Algorytmy i struktury danych/Wyszukiwanie: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 31: | Linia 31: | ||
m:=(l+r) '''div''' 2; | m:=(l+r) '''div''' 2; | ||
'''if''' (A[m]<x) '''then''' l:=m+1 | '''if''' (A[m]<x) '''then''' l:=m+1 | ||
'''else if''' (A[m]>x) '''then''' r:=m-1 | '''else if''' (A[m]>x) '''then''' r:=m-1 | ||
'''else''' | '''else''' '''return''' ''m'' { ponieważ A[m]=x } ; | ||
'''end'''; | '''end'''; | ||
'''return''' ''brak poszukiwanego elementu'' | '''return''' ''brak poszukiwanego elementu'' | ||
Wersja z 08:56, 22 lip 2006
Wyszukiwanie
W niniejszym wykładzie opiszemy podstawowe techniki dotyczące wyszukiwania.
Zajmiemy się również prostymi strukturami słownikowymi, które oprócz
wyszukiwania, umożliwiają dodawanie i usuwanie elementów.
Wyszukiwanie liniowe
TODO
function Szukaj(x, A[1..n])
begin
for i:=1 to n do
if A[i]=x return i
return brak poszukiwanego elementu
end
Wyszukiwanie binarne
TODO
function WyszukiwanieBinarne(x, A[1..n])
{ zakładamy, że tablica A, jest uporządkowana rosnąco }
begin
l:=1;r:=n;
while (l<=r) do begin
m:=(l+r) div 2;
if (A[m]<x) then l:=m+1
else if (A[m]>x) then r:=m-1
else return m { ponieważ A[m]=x } ;
end;
return brak poszukiwanego elementu
end
Drzewa poszukiwań binarnych
TODO
Haszowanie
TODO
