Wyszukiwanie z wartownikiem.

W algorytmie wyszukiwania sekwencyjnego znajduje się pętla wyszukująca. W pętli sprawdzane są dwa warunki. Pierwszy z nich (zaznaczony czerwoną linią na rysunku obok) jest potrzebny tylko wtedy, gdy zbiór d[ ] nie zawiera poszukiwanego elementu o wartości x. W takim przypadku wymieniony warunek gwarantuje zakończenie pętli przeszukującej po przeglądnięciu wszystkich elementów zbioru. Indeks p przyjmuje wartość n + 1. Warunek jest sprawdzany dla każdego elementu zbioru. Jeśli moglibyśmy zagwarantować, iż poszukiwany element zawsze zostanie znaleziony, to wtedy warunek ten stałby się zbędny. Możemy doprowadzić do takiej sytuacji dodając na końcu zbioru poszukiwany element. Wtedy pętla przeszukująca zakończy się albo na elemencie x leżącym wewnątrz zbioru, albo na elemencie x, który został dodany do zbioru. W pierwszym przypadku zmienna p będzie wskazywała pozycję znalezionego elementu i pozycja ta będzie mniejsza lub równa n, a w drugim przypadku (gdy element x w zbiorze nie występuje) zmienna p wskaże pozycję dodanego przez nas elementu, czyli n + 1. Ponieważ pętla ta zawsze zakończy się, to możemy pominąć pierwszy warunek pozostawiając jedynie test na różność od x. Uproszczenie to da w wyniku wzrost prędkości wyszukiwania. Dodany przez nas element na końcu zbioru nosi nazwę wartownika (ang. guard lub sentinel), a stąd pochodzi nazwa algorytmu - przeszukiwanie z wartownikiem. Klasa złożoności obliczeniowej wynosi (n).

Specyfikacja problemu

Dane wejściowe :

n - liczba elementów w zbiorze wejściowym

d[ ] - zbiór wejściowy, w którym dokonujemy poszukiwań. Indeksy elementów rozpoczynają się

od 1. Zbiór musi posiadać miejsce na dodatkowy element, który zostanie dopisany na

końcu.

x - wartość poszukiwana

Dane wyjściowe :

p - pozycja elementu x w zbiorze d[ ]. Jeśli p = 0, to element x w zbiorze nie występuje

Lista kroków

Krok 1 : d[n + 1] := x;

Krok 2 : p := 1;

Krok 3 : Dopóki x < > d[p]: wykonuj p := p + 1

Krok 4 : Jeśli p > n, to p := 0

Krok 5 : Zakończ algorytm

Schemat blokowy

Na samym początku algorytmu dopisujemy do zbioru wartownika. Przeszukiwanie rozpoczynamy od

pierwszego elementu, dlatego p przyjmuje wartość 1. Pętla przeszukująca porównuje kolejne elementy zbioru z wartością poszukiwaną. Jeśli są różne, to przesuwa się do następnej pozycji. Wartownik gwarantuje nam, iż przeszukiwanie zawsze się zakończy. Gdy pętla przeszukująca zostanie zakończona, zmienna p przechowuje pozycję elementu zbioru równego x. Jeśli p wskazuje wartownika, to zbiór nie zawiera poszukiwanego elementu - w takim przypadku zerujemy pozycję p, aby zgłosić porażkę. Kończymy algorytm.

START

d[n+1] := x;

p:= 1;

x <> d[p]

p:= p + 1; p > n

p:= 0;

TAK

TAK NIE

STOP

NIE

Read (x);

---