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++:
#include<iostream>
#include<cstdlib>
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;
system("pause");
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.