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

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

В неупорядоченной последовательности сравненение ключей продолжается до тех пор, пока не будут просмотрены все N записей. Запись с искомым ключом выводится на печать.

Структурограмма алгоритма последовательного поиска в неупорядоченной последовательности записей приведена на рис

Пример. Осуществить последовательный поиск аргумента 32 в

массиве ключей: 37 25 32 29 20.

i = 1: 37 25 32 29 20

i = 2: 37 25 32 29 20

i = 3: 37 25 32 29 20

Подчеркивание означает выбор Ki для сравнения с А.

Поиск окончен удачно, ключ 32 имеет порядковый номер, равный 3.

Пример реализации ?

Возможно ускорение работы последовательного поиска путем добавления в конец набора данных фиктивной записи XN+1 с ключом KN+1, равным аргументу поиска А. Структурограмма алгоритма

последовательного поиска в этом случае будет выглядеть так, как представлена на рис.

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

В последовательности, упорядоченной, например, по возрастанию ключей записей, поиск можно прекратить сразу же, как только значение ключа текущей записи превысит значение аргумента поиска.

Для ускорения в конец списка добавляют фиктивную запись XN+1 с ключом KN+1, превышающим аргумент поиска А. Рис. Пример (на обороте)

Если известно, что записи упорядочены, то существует несколько методов, которые могуть быть использованы для увеличения эффективности поиска.