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

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

Для последовательного поиска в среднем требуется (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;

Бинарный поиск

Другим относительно простым методом доступа к элементу является метод бинарного (дихотомического, двоичного) поиска, который выполняется в заведомо упорядоченной последовательности элементов. Записи в таблицу заносятся в лексикографическом (символьные ключи) или численно (числовые ключи) возрастающем порядке. Для достижения упорядоченности может быть использован какой-либо из методов сортировки (см. 3.9).

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

Для того, чтобы найти нужную запись в таблице, в худшем случае требуется log2(N) сравнений. Это значительно лучше, чем при последовательном поиске.

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

{===== Программный пример 3.5 =====}

Function BinSearch(a : SEQ; key : integer) : integer;

Var b, e, i : integer;

begin

b:=1; e:=N; { начальные значения границ }

while b<=e do { цикл, пока интервал поиска не сузится до 0 }

begin i:=(b+e) div 2; { середина интервала }

if a[i]=key then

begin BinSearch:=i; Exit; {ключ найден - возврат индекса }

end else

if a[i] < key then b:=i+1 { поиск в правом подинтервале }

else e:=i-1; { поиск в левом подинтервале }

end; BinSearch:=EMPTY; { ключ не найден }

end;

Трассировка бинарного поиска ключа 275 в исходной последовательности:

представлена в таблице 3.4.

Таблица 3.4

Алгоритм бинарного поиска можно представить и несколько иначе, используя рекурсивное описание. В этом случае граничные индексы интервала b и e являются параметрами алгоритма.

Рекурсивная процедура бинарного поиска представлена в программном примере 3.6. Для выполнения поиска необходимо при вызове процедуры задать значения ее формальных параметров b и е - 1 и N соответственно, где b, e - граничные индексы области поиска.

{===== Программный пример 3.6 =====}

Function BinSearch( a: SEQ; key, b, e : integer) : integer;

Var i : integer;

begin

if b > e then BinSearch:=EMPTY { проверка ширины интервала }

else begin

i:=(b+e) div 2; { середина интервала }

if a[i]=key then BinSearch:=i {ключ найден, возврат индекса}

else if a[i] < key then { поиск в правом подинтервале }

BinSearch:=BinSearch(a,key,i+1,e)

else { поиск в левом подинтервале }

BinSearch:=BinSearch(a,key,b,i-1);

end; end;

Известно несколько модификаций алгоритма бинарного поиска, выполняемых на деревьях, которые будут рассмотрены в главе 5.