Название этой группы методов произошло от использования последовательного списка в качестве структуры данных для хранения ключей. Список называют упорядоченным, если он упорядочен по значениям ключей, в противном случае он не называется упорядоченным, хотя некоторый порядок ему можно придать за счет размещения в начале списка элементов, которые ищутся наиболее часто, то есть в порядке убывания вероятностей запросов P[1] ... P[N].

Последовательный поиск в неупорядоченном файле
Алгоритм поиска имеет вид:

Рис. 1.  

Время работы алгоритма t примерно оценивается формулой:
,
где a - неизвестная константа, зависящая от программной реализации алгоритма, а также от результата поиска: удачен-неудачен. Среднее время удачного поиска можно значительно сократить, если вероятности появления запросов на поиск различных ключей сильно отличаются друг о друга и ключи располагать в порядке убывания вероятностей. Алгоритм в этом случае не изменяется, но должен быть предварительный этап упорядочения списка. Также предполагается, что новые ключи при неудачном поиске не вставляются в список.

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

Вероятности появления запросов на поиск часто не известны заранее. В этом случае можно использовать эмпирический алгоритм, дающий на практике хорошие результаты: каждый раз при удачном поиске найденный ключ переставляется в начало списка. Естественно такие перестановки удобно делать на связанном списке. Каждому ключу K[i] соответствует поле связи L[i], указывающее на следующий логически за ним ключ. На первый элемент указывает поле связи L[0].

Рис. 2.  

Этот алгоритм легко модифицируется и для случая, когда после неудачного поиска ключ Х должен быть вставлен первым в список. Время работы алгоритма t примерно оценивается формулой:
,
где a - неизвестная константа, зависящая от программной реализации алгоритма, а также от результата поиска: удачен-неудачен.

Последовательный поиск в упорядоченном файле.

Если расположить ключи в возрастающем порядке, то время неудачного поиска можно существенно сократить. В простейшем алгоритме поиска в упорядоченном файле поиск прекращается, если при последовательном просмотре величина Х становится больше или равной очередному ключу K[i]. В среднем при этом сокращается время неудачного поиска до N/2, среднее время удачного поиска остается по-прежнему равным N/2. Алгоритм имеет вид:

Рис. 3.  

Время работы алгоритма t примерно оценивается формулой:
,
где a - неизвестная константа, зависящая от программной реализации алгоритма и не зависящая для данного алгоритма от результата поиска: удачен-неудачен.