УП_САОД_2003

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

Этот алгоритм поиска предполагает, что множество хранится, как некоторая упорядоченная (например, по возрастанию) последовательность элементов, к которым можно получить прямой доступ посредством индекса. Фактически речь идет о том, что множество хранится в массиве и этот массив отсортирован.

Суть метода заключается в следующем. Областью поиска (L, R) назовем часть массива с индексами от L до R, в которой предположительно находится искомый элемент. Сначала областью поиска будет часть массива (L, R), где L = 1, а R = n, то есть вся заполненная элементами множества часть массива. Теперь найдем индекс среднего элемента m := (L+R) div 2. Если Key > A_m, то можно утверждать (поскольку массив отсортирован), что если Key есть в массиве, то он находится в одном из элементов с индексами от L + m до R, следовательно, можно присвоить L := m+1, сократив область поиска. В противном случае можно положить R := m. На этом заканчивается первый шаг метода. Остальные шаги аналогичны.

На каждом шаге метода область поиска будет сокращаться вдвое. Как только L станет равно R, то есть область поиска сократится до одного элемента, можно будет проверить этот элемент на равенство искомому и сделать вывод о результате поиска.

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

function BinarySearch(Key: ItemType, n: integer;

var A: array[1..n] of ItemType): boolean;

{Функция двоичного поиска,}

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

var

L, m, R: integer;

begin

L := 1; R := n;

while (L <> R) do begin

m := (L+R) div 2;

if Key > A[m] then L := m+1

else R := m;

end;

if A[L]=Key then BinarySearch := true

else BinarySearch := false;

end;

Рисунок 26. Бинарный поиск

Как уже было сказано, область поиска на каждом шаге сокращается вдвое, а это означает сложность алгоритма пропорциональную O(log n).

Содержание