Przeszukiwanie liniowe z wartownikiem

powrót

Przeszukiwanie liniowe polega na wyszukaniu pozycji, na której wystąpi pierwszy raz szukana liczba. Może zdarzyć się sytuacja, że ta liczba nie znajduje się w zbiorze.

"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.

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,\ 11,\ 6,\ -1$$

Załóżmy, że chcemy wyszukać liczbę $$2$$. Jak widać znajduje się ona na pozycji $$4$$ 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.

Algorytm można testować na stronie z automatyczną sprawdzarką tutaj.

Rozwiązanie w C++:

//algorytm.edu.pl
#include<iostream>
using namespace std;

int main()
{
    int tab[1001], i = 0, szukana;
    
    //wczytanie elementów tablicy, ostatnim elementem jaki wczytamy jest wartownik = -1
    do{
        cin>>tab[i];
    }while(tab[i++]!=-1);
    
    //podanie liczby do wyszukania
    cin>>szukana;
    
    i = 0;
    //przeszukanie tablicy
    while(tab[i]!=szukana && tab[i]!=-1) ++i;
    //koniec wyszukiwania
    
    //jeśli zatrzymaliśmy się na wartowniku, to oznacza, 
   //że szukana liczba nie występuje w zbiorze    
    if(tab[i] == -1) 
       cout<<"Szukany element nie występuje w tablicy"<<endl;
    else
       cout<<"Liczba "<<szukana<<" znajduje się na pozycji "<<i+1<<endl;
    
    return 0;
}

Złożoność algorytmu jest rzędu O(n). Żeby odnaleźć szukany element w tablicy, w pesymistycznej sytuacji musimy zbadać n elementów.