Последовательный или линейный поиск

Простейшим методом поиска элемента, находящегося в неупоря-

доченном наборе данных, по значению его ключа является последова-

тельный просмотр каждого элемента набора, который продолжается до

тех пор, пока не будет найден желаемый элемент. Если просмотрен

весь набор, но элемент не найден - значит, искомый ключ отсутс-

твует в наборе.

Для последовательного поиска в среднем требуется (N+1)/2

сравнений. Таким образом, порядок алгоритма - линейный - O(N).

{===== Программный пример 3.4 =====}

Function LinSearch( a : SEQ; key : integer) : integer;

var i : integer;

for i:=1 to N do { перебор эл-тов массива }

if a[i]=key then begin { ключ найден - возврат индекса }

LinSearch:=i; Exit; end;

LinSearch:=EMPTY; {просмотрен весь массив, но ключ не найден }

end;

Программная иллюстрация линейного поиска в неупорядоченном

массиве приведена в следующем примере, где a - исходный массив,

key - ключ, который ищется; функция возвращает индекс найденного

элемента или EMPTY - если элементт отсутствует в массиве.