Szukanie elementu
Często spotykanym rodzajem przeszukiwania jest wyszukiwanie
elementu posiadającego pewną szczególną własność, jak np. najmniejszy,
największy, podzielny przez jedenaście - element taki możemy nazwać idealnym.
Algorytm znajdowania elementu idealnego polega na wstępnym przyjęciu, że elementem idealnym jest pierwszy z dostępnych, a następnie na porównywaniu kolejnych elementów z elementem dotychczas uznanym za idealny. Jeśli podczas porównania okaże się, że element porównywany jest bliższy ideałowi niż dotychczasowy ideał, to wykonuje się zamianę przyjmując za ideał element aktualnie porównywany.
Algorytm znajdowania elementu idealnego polega na wstępnym przyjęciu, że elementem idealnym jest pierwszy z dostępnych, a następnie na porównywaniu kolejnych elementów z elementem dotychczas uznanym za idealny. Jeśli podczas porównania okaże się, że element porównywany jest bliższy ideałowi niż dotychczasowy ideał, to wykonuje się zamianę przyjmując za ideał element aktualnie porównywany.
Przeszukiwanie binarne
Przeszukiwanie binarne jest algorytmem sprawdzającym czy
uporządkowany rosnąco ciąg liczbowy N-elementowy zawiera szukaną liczbę x
(nazywane jest też przeszukiwaniem połówkowym).
Algorytm przeszukiwania binarego wykorzystuje uporządkowanie ciągu liczbowego dzieląc go każdorazowo na połowy. Poszukiwaną liczbę x porównuje się z liczbą środkową ciągu i w zależności od wyniku tego porównania przeszukiwana jest albo lewa, albo prawa część tablicy. Obszar poszukiwania wyznaczają dwa indeksy: start i stop. oznaczają one odpowiednio początek i koniec przeszukiwanego fragmentu tablicy - rozpoczynając przeszukiwanie zmiennym tym przypisujemy wartości start:=1 i stop:=N, zakończenie przeszukiwania następuje gdy przeszukiwany fragment tablicy zmaleje do jednego elementu, to znaczy, gdy start=stop.
Algorytm przeszukiwania binarego wykorzystuje uporządkowanie ciągu liczbowego dzieląc go każdorazowo na połowy. Poszukiwaną liczbę x porównuje się z liczbą środkową ciągu i w zależności od wyniku tego porównania przeszukiwana jest albo lewa, albo prawa część tablicy. Obszar poszukiwania wyznaczają dwa indeksy: start i stop. oznaczają one odpowiednio początek i koniec przeszukiwanego fragmentu tablicy - rozpoczynając przeszukiwanie zmiennym tym przypisujemy wartości start:=1 i stop:=N, zakończenie przeszukiwania następuje gdy przeszukiwany fragment tablicy zmaleje do jednego elementu, to znaczy, gdy start=stop.
DANE:
a - przeszukiwana
tablica (posortowana rosnąco)
x - poszukiwana
liczba
N - rozmiar
tablicy
WYNIK:
prawda, jeżeli
tablica "a" zawiera liczbę "x"
- Przyjmij:
start:=1; stop:=N;
- Dopóki
start<stop;
- Wyznacz
środek przedziału sr=(start+stop) Div 2,
- Jeżeli
poszukiwana liczba x jest nie większa niż liczba w środku tablicy, to
odrzuć prawą jej część przyjmując za stop:=sr;
- W
przeciwnym wypadku odrzuć część lewą przyjmując za start:=sr+1;
- Teraz start=stop, zwróć prawdę jeśli a[start]=x
Przeszukiwanie liniowe
Przeszukiwanie liniowe (lub wyszukiwanie
sekwencyjne) to najprostszy algorytm wyszukiwania informacji w ciągu danych, np.
zapisanych w tablicy lub na liście. Polega na
porównywaniu żądanego klucza z kolejnymi kluczami z sekwencji danych –
wyszukiwanie kończy się powodzeniem, gdy zostanie znaleziony klucz, albo
niepowodzeniem, gdy zostaną przejrzane wszystkie klucze.
Liczba koniecznych porównań zależy wprost od położenia
szukanego elementu w sekwencji danych – wynosi od 1 do , gdzie to całkowita liczba elementów. Algorytm ma złożoność .
Wyszukiwanie liniowe może być jedynym sposobem
wyszukiwania, gdy nie wiadomo niczego na temat kolejności kluczy.
Dla dużej liczby danych algorytm jest bardzo
nieefektywny, jednak gdy danych jest względnie mało, jest z powodzeniem
stosowany (np. w tablicach mieszających, w których problem
kolizji rozwiązuje się metodą łańcuchową).
Dodatkowo jeśli wiadomo, że pewne klucze mogą być
wyszukiwane częściej niż inne, można modyfikować kolejność danych, tak aby
ponowne wyszukiwanie tego samego klucza kończyło się powodzeniem szybciej.
Metoda ta nosi nazwę move-to-front, Donald
Knuth wymienia w swojej pracy Sztuka programowania dwie strategie:
- natychmiastowe
przesunięcie znalezionego elementu na początek sekwencji,
- przesunięcie tylko o jedną pozycję w stronę początku sekwencji.
Załóżmy że mamy daną tablicę n-elementów i chcemy odnaleźć w niej
zadany element x. Niech będzie to tablica a o indeksach
od 1 do n. Czyli kolejne jej elementy oznaczymy: a[1],
a[2], a[3], ..., a[n-1], a[n].Jeżeli przyjrzymy się dokładnie klasycznemu algorytmowi
przeglądania tablicy w poszukiwaniuelementu:
zauważymy, że dla każdego elementu wykonywane są dwa
porównania:
- pierwsze:
czy znaleźliśmy się już na końcu tablicy,
- drugie:
czy aktualnie przeglądany element jest równy poszukiwanemu.
Liczbę porównań można zredukować wykorzystując algorytm wyszukiwania z wartownikiem. Nazwa tego algorytmu bierze się ze sposobu, w jaki wykorzystywany jest element szukany x.
By odnaleźć element x podejmiemy następujące kroki:
- na
końcu tablicy (czyli pod indeksem n+1) wstawimy szukany
element x - będzie to nasz wartownik, w przypadku gdy nie
znajdziemy go nigdzie indziej w tablicy, zabezpieczy nas on przed wyjściem
poza tablicę,
- przejdziemy
po kolejnych elementach tablicy, tak długo aż nie znajdziemy szukanego
elementu,
- w
momencie znalezienia szukanego elementu x sprawdzamy,
który jest to element tablicy? Jeżeli jest to ostatni element tablicy (n+1)
to trafiliśmy na naszego wartownika i oznacza to, że w tablicy nie było
szukanego elementu x, w przeciwnym razie element x został
odnaleziony.
Brak komentarzy:
Prześlij komentarz