Простейшим методом поиска элемента, находящегося в неупоря-
доченном наборе данных, по значению его ключа является последова-
тельный просмотр каждого элемента набора, который продолжается до
тех пор, пока не будет найден желаемый элемент. Если просмотрен
весь набор, но элемент не найден - значит, искомый ключ отсутс-
твует в наборе.
Для последовательного поиска в среднем требуется (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 - если элементт отсутствует в массиве.