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

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

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

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

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

==========269

@Рис. 10.2. Двоичный поиск элемента со значением 44

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

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

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

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

Public Function BinarySearch(target As Long) As Long

Dim min As Long

Dim max As Long

Dim middle As Long

NumSearches = 0

' Во время поиска индекс искомого элемента будет находиться

' между Min и Max: Min <= target index <= Max

min = 1

max = NumItems

Do While min <= max

NumSearches = NumSearches + 1

middle = (max + min) / 2

If target = List(middle) Then ' Мы нашли искомый элемент!

BinarySearch = middle

Exit Function

ElseIf target < List(middle) Then ' Поиск в левой половине.

max = middle - 1

Else ' Поиск в правой половине.

min = middle + 1

End If

Loop

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

BinarySearch = 0

End Function

На каждом шаге число элементов, которые еще могут иметь искомое значение, уменьшается вдвое. Для списка размера N, алгоритму может потребоваться максимум O(log(N)) шагов, чтобы найти любой элемент или определить, что его нет в списке. Это намного быстрее, чем в случае применения алгоритма полного перебора. Полный перебор списка из миллиона элементов потребовал бы в среднем 500.000 шагов. Алгоритму двоичного поиска потребуется не больше, чем log(1.000.000) или 20 шагов.