Линейный поиск

Рассмотрим простейшую задачу поиска элемента в массиве.

Дан массив A, состоящий из n элементов, и дано значение x:

var

A: TableType; {Таблица (массив) данных}

x: KeyType; {Искомый элемент}

Требуется определить, содержится ли в массиве A элемент, равный x, и если содержится, то на каком месте (при каком значении индекса массива).

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

function LinearSearch(A: TableType, x: KeyType

): Integer;

var

i: Integer;

begin

i:= 1;

while (i <= N) and (A[i] <> x) do

i:= i+1;

if i <= N then LinearSearch:= i {Успех}

else LinearSearch:= 0; {Неудача}

end; {LinearSearch}

Этот простейший алгоритм называется линейным поиском в массиве. Он сравнивает искомый ключ x последовательно с каждым элементом массива. Функция возвращает индекс найденного элемента либо 0, если ключ не найден в массиве.

В программе намеренно не использован цикл for. Это сделано для более наглядного сравнения с алгоритмом, который будет описан ниже.

Оценим эффективность алгоритма линейного поиска. Очевидно, время его работы будет пропорционально числу элементов в массиве: T(n) = O(n). В таких случаях говорят, что алгоритм имеет линейную оценку относительно размера массива.

Если проанализировать время выполнения более детально, то можно сказать, что максимальное количество итераций равно n (в случае, если искомый ключ находится в последней позиции массива или вообще отсутствует), а среднее число итераций при успешном поиске равно n/2 (искомое значение может с равной вероятностью находиться в любой позиции, в среднем это даст n/2), а при неудаче поиска среднее число итераций равно максимальному n. Важно отметить, что в любом случае число итераций (а стало быть, и время выполнения) остается пропорциональным размеру массива.

Линейная оценка – хорошо это или плохо? Если бы речь шла о какой-либо сложной и редко решаемой задаче, то такая оценка была бы верхом мечтаний. Но для столь массовой задачи, как поиск в таблице, следует поискать более быстрый алгоритм.

Можно добиться некоторого ускорения работы, оставаясь в рамках линейного поиска. Известен, например, полезный прием, который называется барьерным поиском. Для его использования необходимо, чтобы в конце (или в начале) массива оставалось одно свободное место. Поэтому предположим временно, что тип массива описан так:

var TableType1 = array [1..N+1] of RecordType;

При этом число записей по-прежнему равно n, а позиция n+1 не содержит данных. Тогда функция барьерного поиска будет выглядеть следующим образом:

function BarrierSearch(var A: TableType1, x: KeyType

): Integer;

var

i: Integer;

begin

i:= 1;

A[N+1]:= x; {Установка барьера}

while A[i] <> x do

i:= i+1;

if i <= N then BarrierSearch:= i {Успех}

else BarrierSearch:= 0; {Неудача}

end; {BarrierSearch}

Отличие от предыдущего алгоритма заключается в том, что искомый элемент x искусственно добавляется в массив. В результате этого можно быть уверенным, что x будет найден в любом случае. Вопрос только в том, будет ли он найден среди n «настоящих» элементов массива или же встретится только в «искусственной» позиции n+1.

В чем выигрыш от использования барьера? Можно заметить, что это позволило упростить проверку в заголовке цикла. Поскольку же итерация цикла всего-то состояла из двух проверок и одного присваивания, отмена одной из проверок может уменьшить время выполнения процентов на 30. Это не меняет линейного характера оценки O(n), но не стоит пренебрегать существенным улучшением, которое достигается так просто. Однако напомним, что для применения барьера необходимо, чтобы с одного из концов массива была свободная позиция, причем доступная для записи.

Барьерный поиск – это типичный пример «мелкой оптимизации», которая мила сердцу почти каждого программиста, позволяет кое-что выиграть только за счет программистской техники, но не дает кардинального улучшения решения. Чтобы получить более значительное ускорение поиска, надо искать принципиально другой подход.