Wyszukiwanie sekwencyjne z wartownikiem to odmiana wyszukiwania liniowego. Algorytm przegląda elementy zbioru kolejno, od początku, aż znajdzie szukaną wartość.
Różnica polega na tym, że na końcu analizowanego zbioru dodaje się specjalny element zwany wartownikiem. Wartownikiem jest zwykle ta sama wartość, której szukamy.
Po co stosuje się wartownika?
W klasycznym wyszukiwaniu sekwencyjnym w pętli trzeba sprawdzać dwa warunki:
- czy nie przekroczono końca tablicy,
- czy aktualny element jest szukanym elementem.
W wersji z wartownikiem warunek końca tablicy nie jest potrzebny w samej pętli, ponieważ mamy pewność, że szukany element na pewno pojawi się najpóźniej jako wartownik.
Schemat działania
- Na końcu tablicy dodaj szukaną wartość jako wartownika.
- Przeglądaj elementy od początku.
- Zatrzymaj się przy pierwszym elemencie równym szukanej wartości.
- Sprawdź, czy znaleziony indeks należy do właściwej części tablicy, czy wskazuje na wartownika.
Przykład pseudokodu
t[n] = szukana_wartosc
i = 0
while t[i] != szukana_wartosc:
i = i + 1
if i < n:
element znaleziony
else:
element nie występuje w zbiorze
Ważne cechy
- Zbiór danych nie musi być uporządkowany.
- Liczba elementów może być dowolna.
- Szukany element nie musi występować wielokrotnie.
- Złożoność czasowa pozostaje liniowa: O(n).
- Wartownika umieszcza się na końcu analizowanego zbioru.