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.