Algorytmy i struktury danych/Wyszukiwanie: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
| Linia 16: | Linia 16: | ||
'''begin''' | '''begin''' | ||
'''for''' i:=1 '''to''' ''n'' '''do''' | '''for''' i:=1 '''to''' ''n'' '''do''' | ||
'''if''' A[i]=x '''return''' ''i'' | '''if''' A[i]=x '''return''' ''i''; | ||
'''return''' ''brak poszukiwanego elementu'' | '''return''' ''brak poszukiwanego elementu''; | ||
'''end''' | '''end''' | ||
Wersja z 08:57, 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
