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 poszukiwaniu elementu:



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.

W stosunku do klasycznego algorytmu wyszukiwania oszczędzamy czas na sprawdzaniu czy osiągnęliśmy koniec tablicy. Sprawdzenie to występuje raz - po odnalezieniu elementu szukanego, a nie tak jak poprzednio przed każdym sprawdzeniem kolejnego elementu.
Operację odnajdowania elementu w tablicy z wartownikiem możemy zapisać następującym schematem blokowym:



Algorytm ten mimo, że jest szybszy od zwykłego wyszukiwania to ma taką samą jak on złożoność obliczeniową wynoszącą O(n), co oznacza, że czas potrzebny na wyszukanie elementu tą metodą rośnie w sposób liniowy wraz z liniowym wzrostem liczby elementów w przeszukiwanej tablicy. To znaczy, że czas potrzebny na wyszukanie dwa razy większej liczby elementów wzrośnie dwukrotnie.
Podczas implementowania tego rozwiązania należy zapewnić miejsce w tablicy potrzebne do dodania wartownika. Należy więc deklarować tablicę o rozmiarze o jeden większym jak liczba przechowywanych elementów.


Niech będzie dana tablica 5-elementowa, a = {4, 6, 2, 1, 3}.
Poszukajmy w niej element x = 2.
Dodajemy na końcu tablicy element o wartości 2, czyli a[6] = 2.
Przeglądamy kolejne elementy tablicy:
a[1] = x? 4 nie jest równe 2, przechodzimy do kolejnego elementu,
a[2] = x? 6 nie jest równe 2, przechodzimy do kolejnego elementu,
a[3] = x? 2 jest równe 2, element znaleźliśmy pod indeksem 3, nie jest to ostatni element tablicy zatem znaleźliśmy szukany element.

Poszukajmy teraz element x = 5.
Dodajemy na końcu tablicy element o wartości 5, czyli a[6] = 5.
Przeglądamy kolejne elementy tablicy:
a[1] = x? 4 nie jest równe 5, przechodzimy do kolejnego elementu,
a[2] = x? 6 nie jest równe 5, przechodzimy do kolejnego elementu,
a[3] = x? 2 nie jest równe 5, przechodzimy do kolejnego elementu,
a[4] = x? 1 nie jest równe 5, przechodzimy do kolejnego elementu,
a[5] = x? 3 nie jest równe 5, przechodzimy do kolejnego elementu,
a[6] = x? 5 jest równe 5, element znaleźliśmy pod indeksem 6, jest to ostatni element tablicy zatem nie znaleźliśmy szukanego elementu a jedynie natrafiliśmy na naszego wartownika, który zabezpieczył nas przed wyjściem poza zakres tablicy. Werdykt zatem brzmi: elementu 5 nie ma w przeszukiwanej tablicy.

Tablica liczb (wartości oddzielone przecinkiem, bez spacji):
Szukana wartosc: