2.3. Алгоритмы поиска

Поиск – процесс отыскания информации во множестве данных (обыч­но представляющих собой записи) путем просмотра специального поля в каждой записи, называемого ключом. Целью поиска является отыска­ние записи (если она есть) с данным значением ключа.

Поиск – одно из наиболее часто встречающихся в программирова­нии действий. Существует множество различных алгоритмов этого дей­ствия, принципиально зависящих от способа организации данных. Да­лее рассмотрены алгоритмы поиска в различных структурах данных.

2.3.1. Поиск в линейных структурах

При дальнейшем рассмотрении поиска в линейных структурах опре­делим, что множество данных, в котором производится поиск, описы­вается как массив фиксированной длины:

A: array[1..n] of ItemType;

Обычно тип ItemType описывает запись с некоторым полем, игра­ющим роль ключа, а сам массив представляет собой таблицу. Так как здесь рассматривается, прежде всего, сам процесс поиска, то будем счи­тать, что тип ItemType включает только ключ.

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

Последовательный поиск – самый простой из известных. Суть его заключается в следующем. Множество элементов просматривается пос­ледовательно в некотором порядке, гарантирующем, что будут просмот­рены все элементы множества (например, слева направо). Если в ходе просмотра множества будет найден искомый элемент, просмотр пре­кращается с положительным результатом; если же будет просмотрено все множество, а элемент не будет найден, алгоритм должен выдать отрицательный результат.

Именно так поступает человек, когда ищет что-то в неупорядочен­ном множестве. Таким образом, данный алгоритм можно применять

89

тогда, когда нет никакой дополнительной информации о расположении данных в рассматриваемой последовательности.

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

function LineSearch(Key: ItemType, n: integer;

var A: array[1..n] of ItemType): boolean; {Функция линейного поиска,}

{если элемент найден, то возвращает значение true, иначе – false} var

i: integer; begin

i := 1;

while (i <=n ) and (A[i]<>Key) do i := i + 1;

if A[i]=Key then LineSearch := true

else LineSearch := false; end;

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

Здесь можно хранить множество как в массиве (как показано выше), так и в обычном однонаправленном списке.

Существует модификация алгоритма последовательного поиска, ко­торая ускоряет поиск.

Эта модификация поиска является небольшим усовершенствова­нием предыдущего. В любой программе, имеющей циклы, наиболь­ший интерес представляет оптимизация именно циклов, т. е. сокра­щение числа действий в них. Посмотрим на алгоритм последова­тельного поиска. В цикле while производятся два сравнения: (i<=n) и (A[i]<>Key). Избавимся от одного из них (от первого), введя в массив так называемый «барьер», положив A[n+1] := Key. В этом случае в цикле обязательно будет найден элемент со значением Key. После завершения цикла требуется дополнительная проверка того, был ли найден искомый элемент, или «барьер».

Тогда функция поиска будет выглядеть так:

function LineSearchWithBarrier(Key: ItemType, n: integer; var A: array[1..n+1] of ItemType): boolean;

90

{Функция линейного поиска с барьером,}

{если элемент найден, то возвращает значение true, иначе – false}

var

i: integer; begin

I := 1;

A[n+1] := Key;

while A[i]<>Key do I := I + 1;

if I <= n then LineSearchWithBarrier := true

else LineSearchWithBarrier := false; end;

Надо сказать, что хотя такая функция будет работать быстрее, но временная сложность алгоритма остается такой же – O(n). Гораздо боль­ший интерес представляют методы, не только работающие быстро, но и реализующие алгоритмы с меньшей сложностью. Один из таких мето­дов – бинарный поиск.