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

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

Простейшим методом поиска элемента, находящегося в неупорядоченном наборе данных, по значению его ключа является последовательный просмотр каждого элемента набора, который продолжается до тех пор, пока не будет найден желаемый элемент. Если просмотрен весь набор, но элемент не найден - значит, искомый ключ отсутствует в наборе.

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

Программная иллюстрация линейного поиска в неупорядоченном массиве приведена в следующем примере, где a - исходный массив, key - ключ, который ищется; функция возвращает индекс найденного элемента или EMPTY - если элементт отсутствует в массиве.

{===== Программный пример 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;