2. Двоичный поиск

Как уже упоминалось в предыдущих разделах, поиск полным перебором выполняется очень быстро для небольших списков. Большие списки намного быстрее обрабатывает алгоритм двоичного поиска (binary search) . Алгоритм двоичного поиска сравнивает элемент в середине списка с искомым. Если искомый элемент меньше, алгоритм продолжает перебирать первую половину списка, если же он больше, чем найденный элемент, поиск продолжается во второй половине списка.

На рисунке 2 процесс поиска элемента со значением 44 изображен графически.

Рисунок 2 – Двоичный поиск элемента со значением 44

Хотя этот алгоритм естественно рекурсивен, его довольно просто записать без рекурсии. Поскольку он достаточно прост для понимания, здесь приводится не рекурсивная версия, которая содержит меньше вызовов функции.

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

Для отслеживания минимального и максимального индекса записей части массива, которая может содержать искомый элемент, алгоритм использует две переменные - min и max. Во время выполнения алгоритма индекс искомого элемента всегда будет находиться между значениями min и max. Другими словами, min <= индекс элемента <=max.

Во время каждого прохода алгоритм присваивает middle = (min + max) / 2 и проверяет ячейку с индексом middle. Если ее значение равно искомому, то цель найдена и алгоритм завершает свою работу. Если искомый элемент меньше, то алгоритм устанавливает max = middle - 1 и продолжает поиск. Поскольку индексы элементов, которые могут содержать искомый элемент, находятся теперь в диапазоне от min до middle - 1, программа перебирает первую половину списка.

Если искомый элемент больше, чем средний, программа устанавливает значение переменной min = middle + 1 и продолжает поиск. Диапазон элементов, который может содержать искомый элемент, лежит теперь в пределах от middle + 1 до max, поэтому программа продолжает поиск во второй половине списка.

В конце концов, программа либо найдет элемент, либо наступит момент, когда значение переменной min будет больше, чем значение max. Значения min и max постоянно корректируются таким образом, чтобы индекс искомого элемента находился всегда между ними. Поскольку в данной точке больше нет индексов между min и max, элемента в списке нет.

Следующий код демонстрирует выполнение двоичного поиска в программе Search:

function BinarySearch (target : Longint; List : PLongArray;

min, max : Longint) : Longint;

var

middle : Longint;

begin

searches := 0;

// Во время поиска индекс искомого элемента будет между min и max:

// min <= искомый индекс <= max.

while (min <= max) do

begin

searches := searches + 1;

middle := Round ((max+min) / 2);

if (target = list^[middle]) then // Мы нашли его.

begin

Result := middle;

exit;

end else if target < List[middle] then

// Перебираем левую половину.

max := middle - 1

else

// Перебираем правую половину.

min := middle + 1;

end;

// Если мы оказались здесь, то искомого элемента в списке нет.

Result := 0; .

end;

На каждом шаге алгоритм сокращает число элементов, которые все еще могут содержать искомый элемент, вполовину. Для списка размера N алгоритму потребуется максимум O(logN) шагов, чтобы найти любой элемент или определить, что его нет в списке. При этом двоичный поиск работает намного быстрее, чем полный перебор. Полный перебор списка из миллиона элементов занимает в среднем 500 000 шагов. Алгоритму ДВОИЧНОГО поиска потребуется максимум log(l 000 000), или 20 шагов.