ВВЕДЕНИЕ
В данной работе рассматривается несколько алгоритмов для поиска (search) элементов в сортированных списках. Она начинается с краткого описания поиска методом полного перебора. Хотя данный алгоритм работает не так быстро, как другие алгоритмы, он очень прост, что облегчает его написание и отладку.
Данный алгоритм очень удобен для обработки совсем небольших списков. Далее в работе описан двоичный поиск. Для того чтобы найти элемент, двоичный поиск несколько раз разбивает список на части, при этом в больших списках такой поиск выполняется намного быстрее, чем полный перебор. Идея, которая лежит в основе метода, достаточно проста, но реализовать ее гораздо сложнее. Затем описывается интерполяционный поиск. Как и двоичный поиск, интерполяционный поиск многократно разбивает список на части. При использовании такого поиска алгоритм делает предположения о том, где должен находится искомый элемент, поэтому для списков, в которых элементы распределены равномерно, он выполняется намного быстрее, чем двоичный поиск. В конце работы рассматриваются методы следящего поиска. Применение этого метода иногда уменьшает время поиска в несколько раз.
1. Полный перебор
Чтобы выполнить полный, или последовательный, перебор (exhaustive search), поиск ведется с начала списка, и элементы перебираются последовательно, пока не будет найден искомый.
type
TLongArray = array [1..10000000] of Longint;
ELongArray = ^TLongArray;
function LinearSearch(target : Longint; List : PLongArray;
min, max : Longint) : Longint;
var
i : Longint;
begin
for i : = min to max do
if (list^[i] = target) then
begin
// Нашли.
Result := I
exit;
end;
// Элемента в списке нет.
Result := 0
and;
Поскольку этот алгоритм исследует список по порядку, он ищет элементы в начале списка быстрее, чем элементы, находящиеся в конце. Наихудший случай для этого алгоритма возникает, когда элемент заканчивает список или вообще отсутствует. Так как алгоритм исследует все элементы списка, время его выполнения в наихудшем случае составляет порядка O(N). Если элемент содержится в списке, то алгоритм должен в среднем исследовать N / 2 записей до того, как обнаружит искомую. Таким образом, в усредненном случае поиск осуществляется также за время порядка O(N). Хотя алгоритмы, которые выполняются за время порядка O(N), нельзя назвать быстрыми, этот алгоритм достаточно прост и дает неплохие результаты на практике. Для небольших списков данный алгоритм показывает приемлемую производительность.
Рисунок 1 – Окно программы Search
1.1 Перебор сортированных списков
Если список сортирован, то можно немного изменить алгоритм полного перебора, чтобы улучшить его производительность. Если во время поиска алгоритм находит элемент со значением большим, чем значение искомого элемента, то он завершает свою работу. Следовательно, искомый элемент не находится в списке, так как иначе он бы встретился раньше. Например, предположим, что вы ищете значение 12 и доходите до значения 17. Вы пропустили позицию, где должен стоять элемент 12, поэтому можно сказать, что значения 12 в списке нет. Следующий код демонстрирует улучшенный алгоритм полного перебора:
function LinearSearch (target : Longint; List : PLongArray;
min, max : Longint) : Longint;
var
I : Longint;
begin
for I := min to max do
if (list^[i] >= target) then break;
if (i > max) then
Result := 0
else if (list^[i] = target) then
Result := I
else
Result := 0;
end;
Эта модификация уменьшает время выполнения алгоритма, если искомого элемента нет в списке. Предыдущая версия поиска при отсутствии элемента проверила бы весь список до конца. Этот же алгоритм останавливается, как только находит элемент больший, чем искомый. Если искомый элемент расположен случайно между минимальным и максимальным элементами списка, алгоритму в среднем потребуется N / 2 шагов, чтобы определить, что элемента в списке нет. Сложность все еще равна O(N), но в действительности алгоритм работает быстрее. Программа Search использует улучшенную версию алгоритма.