"Wartownik" - to taka wartość, którą ustawiamy na końcu zbioru. Cechuje się ona tym, że nie występuje w badanym ciągu. Jeśli na nią natrafimy to mamy pewność, że przeszukaliśmy już cały zbiór i szukana wartość nie istnieje.
2. Przykład.
W naszym przykładzie zakładamy, że zbiór składa się z liczb naturalnych. Ilość liczb jest mniejsza od 1000 Jako wartownik posłuży nam liczba -1 (nie jest to liczba naturalna i nie wystąpi wcześniej).
Prześledźmy przykład:
9, 0, 8, 2, 1, 6, -1
Załóżmy, że chcemy wyszukać liczbę 2. Jak widać znajduje się ona na 4 pozycji i ta liczba powinna znaleźć się na wyjściu.
Gdy spróbujemy wyszukać liczbę 7, algorytm zatrzyma się na wartości wartownika. Na wyjściu powinien pojawić się stosowny komunikat.
Brak komentarzy:
Prześlij komentarz