Przeszukiwanie ciągu liczbowego

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.

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.

  DANE:

     a - przeszukiwana tablica (posortowana rosnąco)

     x - poszukiwana liczba

     N - rozmiar tablicy

  WYNIK:

  prawda, jeżeli tablica "a" zawiera liczbę "x"

1. Przyjmij: start:=1; stop:=N;
2. 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;
3. 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:

1. natychmiastowe przesunięcie znalezionego elementu na początek sekwencji,
2. przesunięcie tylko o jedną pozycję w stronę początku sekwencji.

Przeszukiwanie ciągu liczbowego z wartownikiem

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.