Liniowe przeszukiwanie ciągu liczbowego

Problem

W n-elementowym zbiorze Z wyszukać element posiadający pożądane własności.

Wyszukiwanie liniowe (ang. linear search), zwane również sekwencyjnym (ang. sequential search) polega na przeglądaniu kolejnych elementów zbioru Z. Jeśli przeglądany element posiada odpowiednie własności (np. jest liczbą o poszukiwanej wartości), to zwracamy jego pozycję w zbiorze i kończymy. W przeciwnym razie kontynuujemy poszukiwania aż do przejrzenia wszystkich pozostałych elementów zbioru Z.

W przypadku pesymistycznym, gdy poszukiwanego elementu nie ma w zbiorze lub też znajduje się on na samym końcu zbioru, algorytm musi wykonać przynajmniej n obiegów pętli sprawdzającej poszczególne elementy. Wynika z tego, iż pesymistyczna klasa złożoności obliczeniowej jest równa O(n), czyli jest liniowa – stąd pochodzi nazwa metody wyszukującej.

Często chcemy znaleźć wszystkie wystąpienia w zbiorze poszukiwanej wartości elementu. W takim przypadku algorytm na wejściu powinien otrzymywać dodatkowo pozycję (indeks) elementu, od którego ma rozpocząć wyszukiwanie. Pozycję tę przy kolejnym przeszukiwaniu podajemy zawsze o 1 większą od ostatnio znalezionej. Dzięki temu nowe poszukiwanie rozpocznie się tuż za poprzednio znalezionym elementem.

Algorytm wyszukiwania liniowego/sekwencyjnego

Wejście

n	–	liczba elementów w tablicy Z, n N
Z	–	tablica zawierająca elementy do przeszukania. Indeksy elementów rozpoczynają się od 0, a kończą na n-1
p	–	indeks pierwszego elementu Z, od którego rozpoczniemy poszukiwania. p C
k	–	poszukiwana wartość, czyli tzw. klucz, wg którego wyszukujemy elementy w Z

Wyjście:

Pozycja elementu zbioru Z o kluczu k lub -1 w przypadku nie znalezienia elementu.

Zmienne pomocnicze

i

–

przebiega przez kolejne indeksy elementów Z. i C

Lista kroków:

K01:	Dla i = p,p+1,...,n-1: wykonuj K02	; przeglądamy kolejne elementy w zbiorze
K02:	Jeśli Z[i] = k, to zakończ z wynikiem i	; jeśli napotkamy poszukiwany element, zwracamy jego pozycję
K03:	Zakończ z wynikiem -1	; jeśli elementu nie ma w tablicy, zwracamy -1