Курс Harvard CS50 - Лекция: Бинарный поиск

Представьте, что у вас есть список отсортированных по алфавиту диснеевских героев, и вам нужно найти Микки Мауса.

Линейно это было бы долго. А если воспользоваться «методом разрывания справочника пополам», мы попадаем сразу на Jasmine, и можем смело отбросить первую половину списка, понимая, что Mickey там не может быть.

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

Давайте найдем число 144. Делим список пополам, и попадаем на число 13. Оцениваем, больше или меньше искомое число, чем 13.

13 < 144, так что мы можем игнорировать всё, что находится левее 13 и само это число. Теперь наш список поиска выглядит так:

Тут чётное число элементов, поэтому выбираем принцип, по которому выбираем «среднее» (ближе к началу или концу). Допустим, мы избрали стратегию близости к началу. В таком случае, наша «середина» = 55.

55 < 144. Мы снова отбрасываем левую половину списка. К счастью для нас, следующее среднее число и будет 144.

Мы нашли 144 в массиве из 13 элементов с помощью бинарного поиска всего за три шага. Линейный поиск в такой же ситуации справился бы аж за 12 шагов. Поскольку этот алгоритм на каждом шаге уменьшает количество элементов в массиве вдвое, он найдет искомое за асимптотическое время О(log n), где n – количество элементов в списке. То есть, в нашем случае асимптотическое время = O(log 13) (это чуть больше трёх).

Псевдокод функции бинарного поиска:

binarySearch(key, array[], min, max):

if (max < min):
return -1 
else: 
midpoint = findMidPoint(min, max)
	
if (array[midpoint] < key): 
binarySearch(key, array, midpoint + 1, max)
else if (array[midpoint] > key):
binarySearch(key, array, min, midpoint - 1)
else:
return midpoint

Функция принимает на вход 4 аргумента: искомое key, массив данных array[], в котором находится искомое, min и max — указатели на максимальное и минимальное число в массиве, на которое мы смотрим на данном шаге алгоритма.

Для нашего примера изначально дана такая картинка:

Разберем код далее. midpoint — наша середина массива. Она зависит от крайних точек и находится по центру между ними. После того, как мы нашли середину, проверяем, меньше ли она нашего числа key.

midpoint = findMidPoint(min, max)

if (array[midpoint] < key):
binarySearch(key, array, midpoint + 1, max)

Если это так, то key также больше, чем любое из чисел левее середины, и мы можем вызвать бинарную функцию снова, только теперь наш min = midpoint + 1. Если окажется, что key < midpoint, мы можем отбросить само это число и все числа, лежащие справа от него. И мы вызываем бинарный поиск по массиву от числа min и вплоть до значения (midpoint – 1).

else if (array[midpoint] > key):
binarySearch(key, array, min, midpoint - 1)

Третья ветка: если значение в midpoint не больше и не меньше, чем key, ему ничего не остается, как быть искомым числом. Его мы и возвращаем в таком случае и заканчиваем работу программы.