Линейный (последовательный) поиск
Линейный поиск – самый простой из известных способов.
Суть его заключается в следующем. Множество элементов просматривается последовательно в некотором порядке, гарантирующем, что будут просмотрены все элементы множества (например, слева направо). Если в ходе просмотра множества будет найден искомый элемент, просмотр прекращается с положительным результатом; если же будет просмотрено все множество, а элемент не будет найден, алгоритм должен выдать отрицательный результат.
Именно так поступает человек, когда ищет что-то в неупорядоченном множестве. Например, при поиске нужной визитки в некотором неупорядоченном множестве визиток человек просто перебирает все визитки в поисках нужной.
Приведем алгоритм последовательного поиска, знакомый всем программистам.
Пусть множество хранится в первых N элементах массива Х. При этом не важен тип элементов множества, важна лишь возможность проверки эквивалентности элемента множества искомому элементу Key.
Функция Locate возвращает номер искомого ключа или N+1, если ключ не найден.
Function Locate(x:vector; k: <тип ключа>): integer;
var i:integer;
begin
i:=1;
while (i<=N) and (k<>x[i]) do inc(i);
Locate:=i
end;
Анализ работы этого алгоритма не представляет труда.
Время работы зависит от количества сравнений ключей С и параметра успеха S =1 при удаче и 0 при неудаче. Последовательный поиск, реализованный на массиве, производит N сравнений для неуспешного поиска, и в среднем N/2 сравнений для успешного. Это означает сложность алгоритма поиска T(n). Для неуспешного поиска это свойство выводится прямо из программного кода: каждая запись должна быть проверена, чтобы установить факт того, что данный ключ не найден.
Для успешного поиска, если мы предположим, что любая из записей имеет равную вероятность быть искомой, то среднее количество сравнений будет:
(1+2+...+N)/N = (N+1)/2 N/2
Единственное требование к способу хранения множества – существование некоторого порядка на множестве: чтобы можно было указать, что один элемент предшествует другому. Здесь можно хранить множество как в массиве (рассмотренный выше кусок программы), так и в обычном однонаправленном списке.
Одно из преимуществ второй реализации состоит в том, что связанный список легко держать сортированным, что ведет к более быстрой версии этого алгоритма:
Type
PListItem = ^TListItem;
TListItem = record
Item: TItem;
Next: PListItem;
end;
Быстрый последовательный поиск
Этот метод поиска является небольшим усовершенствованием предыдущего с помощью граничного элемента.
В любой программе, имеющей циклы, наибольший интерес представляет оптимизация именно циклов, то есть сокращение числа действий в них.
Здесь использован принцип: если во внутреннем цикле программы проверяются два или более условия, нужно постараться оставить только одно сравнение.
В цикле while производится два сравнения: (i<=n) и (A[i]<>Key). Избавимся от одного из них (от первого), положив A[n+1]:= Key. Другими словами, достаточно просто дописать новый элемент в «конец» множества.
Тогда функция поиска будет выглядеть так:
Function Locate(x:vector; k: integer): integer;
var i:integer;
begin
i:=1; x[n+1]:=K;
while K<>x[i] do inc(i);
Locate:=i
end;
При поиске по большим таблицам скорость улучшенного алгоритма увеличивается на 30% по сравнению с первым вариантом.Надо сказать, что хотя такой фрагмент кода будет работать быстрее, но его теоретическая сложность остается такой же – T(n).
Бинарный (двоичный) поиск
Гораздо больший интерес представляют методы, не только работающие быстро, но и дающие лучшую теоретическую сложность. Один из таких методов – дихотомический поиск.
Этот метод поиска предполагает, что множество хранится, как некоторая отсортированная (например, по возрастанию) последовательность элементов, к которым можно получить прямой доступ посредством индекса. Фактически речь идет о том, что множество хранится в массиве и этот массив отсортирован.
Суть метода заключается в следующем. Сначала К сравнивается со средним ключом в таблице, результат сравнения позволяет определить в какой половине таблицы следует продолжить поиск, применяя к ней ту же процедуру и т.д.
Рассмотрим этот метод более подробно. Областью поиска (l, r) назовем часть массива с индексами от l до r, в которой предположительно находится искомый элемент.
Сначала областью поиска будет часть массива (l, r), где l=1, а r=n, то есть вся заполненная элементами множества часть массива.
Теперь найдем индекс среднего элемента m=(l+r) div 2.
Если Key>A[m], то можно утверждать (поскольку массив отсортирован), что если Key есть в массиве, то он находится в одном из элементов с индексами от m+l до r, следовательно, можно присвоить l=m+1, сократив область поиска.
В противном случае можно положить r=m. На этом заканчивается первый шаг метода. Остальные шаги аналогичны.
На каждом шаге метода область поиска будет сокращаться вдвое. Как только l станет равно r, то есть область поиска сократится до одного элемента, можно будет проверить этот элемент на равенство искомому и сделать вывод о результате поиска.
Бинарный поиск является методом непоследовательного поиска и известен также как метод половинного деления или дихотомии.
Функция Locate возвращает номер искомого ключа или N+1, если ключ не найден.
Function Locate(x:vector; k: integer): integer;
var l, r, i: integer;
begin
l:=1; r:=N;
repeat
i:=(L+r) div 2;
if K>x[i] then l:=i+1
else if K<x[i] then r:=i-1
until (K=x[i]) or (l>r);
if K=x[i] then Locate:= i else Locate:=N+1
end;
Бинарный поиск, никогда не использует более чем log2N+1 сравнений как для успешного, так и для неуспешного поиска. А это означает сложность T(log(n)).
Это свойство следует из того, что количество обрабатываемых записей в каждом цикле сокращается вдвое. Количество производимых при этом сравнений равно CN= CN/2+1 при C1= 1, что доказывает данное свойство.
Добавление граничного элемента дает усовершенствованный вариант алгоритма:
Function Locate(x:vector; k: integer): integer;
var l, r, i: integer;
Begin
l:=1; r:=N; x[N+1]:=K;
repeat
i:=(L+r) div 2;
if K>x[i] then l:=i+1
else if K<x[i] then r:=i-1
until K=x[i];
Locate:=i
end;
Интерполяционный поиск
Рассмотрим еще один метод, имеющий хорошую теоретическую сложность. Как и предыдущий, этот метод предполагает, что множество хранится в массиве и массив отсортирован. Как и предыдущий метод, этот на каждом шаге своей работы сокращает область поиска. Но в отличие от предыдущего метода проба берется не в середине рассматриваемой области.
Пусть имеется область поиска (l, r). Предположим, что элементы множества – целые числа, возрастающие в арифметической прогрессии. Тогда искомый элемент должен находиться в массиве (если он вообще там есть) под индексом:
.
Это следует из свойств арифметической прогрессии. В этом элементе и будем брать пробу.
l:= 1; r:= n;
while (l<>r) do
begin
m:= l+(r-l)*(Key-A[l])/(A[r]-A[l]);
if Key>A[m] then l:= m+1 else r:= m;
end;
if A[l]=Key then <элемент найден> else <элемент не найден>;
Мы сделали очень большое допущение, предположив, что элементы массива представляют собой возрастающую арифметическую прогрессию. В реальности такая ситуация встречается редко. Но этот метод хорошо работает для любых пусть не идеально, но более-менее равномерно распределенных данных.
Если же мы имеем дело с неравномерно распределенными данными, то интерполяционный поиск может увеличить число шагов по сравнению с дихотомическим поиском.
Теоретическая сложность интерполяционного поиска – T(log(log(n))). Это, конечно, лучше, чем сложность дихотомического поиска, но эти преимущества становятся достаточно заметными лишь при очень больших значениях n. Практически на всех реальных n разница между дихотомическим и интерполяционным поиском по скорости не существенна.
Контрольные вопросы
1. Почему последний из разобранных методов поиска называется интерполяционным?
2. Почему при хранении в списке невозможно воспользоваться дихотомическим и интерполяционным поиском?