Бинарный поиск
Про бинарный поиск можно говорить очень долго, так как этот алгоритм несмотря на свою простоту обладает поистине мощным применением, и сама идея, лежащая в основе, тоже является незаменимой в багаже знаний любого программиста.
Начнем мы с небольшого описания алгоритма. Суть бинарного поиска в том, что мы делим какое-то множество на две примерно равные части и, анализируя элемент по середине, отбрасываем либо первую, либо вторую половину, далее продолжаем поиск рекурсивно в выбранной части множества. Уже можно догадаться, что алгоритм работает только тогда, когда можно выбрать этот "средний" элемент - тем самым необходима, например, упорядоченность рассматриваемого множества. Чтобы разобраться лучше, сейчас мы рассмотрим несколько задач, для которых бинарный поиск крайне эффективен, а иногда является единственным решением.
Поиск элемента в массиве
Пусть нам дан упорядоченный массив, который в процессе не будет изменяться. И допустим, к нему приходит множество запросов на проверку того, что лежит ли какой-то элемент массиве или нет. Эту задачу мы решим с помощью бинарного поиска, который намного быстрее обычного линейного поиска, работающего в худшем случае за .
Итак, суть все та же - выбираем средний элемент в массиве, сравниваем его с нужным элементом и отбрасываем либо левую часть массива, либо правую, потом запускаем ту же процедуру над нужной половиной. В конце мы придем к массиву длинной 1, и нам останется проверить только равенство этого одного элемента с данным. Приведем главную часть кода:
# массив array отсортирован по возрастанию
def bin_search(array, elem):
# если массив пустой, то никакого элемента там точно нет
if len(array) < 1:
return False
# самый простой случай - массив состоит из одного элемента
# сравниваем этот элемент с нужным
if len(array) == 1:
return array[0] == elem
# тут идет выбор "среднего"
m = len(array) // 2
# если мы уже нашли элемент, то почему бы сразу не понять это
if array[m] == elem:
return True
# сравниваем "средний" элемент с данным
# и понимаем какую половину массива следует нам отбросить
if array[m] < elem:
# если "средний" элемент меньше нужного, мы отбрасываем левую половину
# так как все элементы в ней заведомо меньше
return bin_search(array[m + 1:], elem)
else:
# аналогично для правой, где все элементы больше
return bin_search(array[:m], elem)
Эту рекурсию естественным образом можно переписать в цикл, который будет работать оптимальнее по времени и памяти.
# массив опять отсортирован по возрастанию
def bin_search(array, elem):
# теперь мы будем поддерживать отрезок индексов [l, r),
# в котором должен быть нужный элемент
# если элемент есть в массиве, то он точно будет в этом отрезке
l = 0
r = len(array)
# если отрезок с самого начала пустой, то нашего элемента там точно нет
if r == 0:
return False
# сужаем наш отрезок, пока не останется один элемент
while l <= r:
# как обычно выбираем "средний" элемент и сравниваем его с нужным
m = (l + r) / 2
# если средний элемент меньше, отбрасываем левую половину
# сдвигая левый конец отрезка l в середину m
if array[m] <= elem:
l = m
else:
# аналогично, сдвигаем правый конце в середину
# отбрасывая правую половину
r = m
# и в конце проверяем содержит ли наш отрезок нужный элемент
return array[l] == elem
Настало время исследовать скорость работы данного алгоритма. Допустим мы запускаем поиск на массиве длины . Как уже говорилось ранее, каждая итерация бинарного поиска отбрасывает половину рассматриваемого массива, то есть после первого шага длина массива, в котором осуществляется поиск, будет равной , после второго - ... после k-ого шага - (Мы используем целочисленное деление, которое отбрасывает остаток. Эта небольшая погрешностью не повлияет на конечную оценку. К тому же, все это можно доказать строже, но я и не стремлюсь к этому. Просто для понимания, почему так и не иначе, такого объяснения вполне достаточно.) В конце наш алгоритм должен сойтись к одному элементу, если это произошло на итерации , то и , то есть . В итоге сложность алгоритма будет , учитывая константу от целочисленного деления и других операций на каждом шаге.
Поиск значения функции на отрезке
Перейдем теперь к следующей задаче, в которой бинарный поиск по-настоящему незаменим. Рассмотрим монотонную функцию (для простоты она будет возрастать) на каком-нибудь отрезке, и опять требуется искать на этом отрезке определенные значения.
Сразу же можно представить, что у нас есть бесконечный отсортированный массив, в котором индексы - это точки на отрезке, а содержимое массива - значения функции, только этот массив задан не явно, а посредством формулы. После этого наблюдения это задачу легко свести к бинарному поиску, но с одним замечанием: так как массив у нас бесконечный, то и бинарный поиск будет работать бесконечно. Эту проблему обычно обходят с помощью задания желаемой точности ответа, либо делают какое-то заданное количество итераций алгоритма. Первый вариант более гибкий, а второй более точный из-за вечной проблемы со сравнением вещественных чисел в компьютере. Приведу реализацию первого случая, но его будет легко переписать и с учетом второго условия.
# (l, r) - отрезок на котором нужно найти такое x, что f(x) = y
def bin_search(l, r, f, y):
# задаем нужную точность ответа
eps = 1e-10
# ответ точно лежит, между l и r, если разница между ними станет меньше eps,
# то полученное нами число будет отличатся от ответа не больше чем на eps
while abs(r - l) > eps:
# как обычно делим отрезок пополам и сравниваем середину с x,
# отбрасывая ненужную половину
m = (r + l) / 2
if f(m) < y:
l = m
else:
r = m
#возвращаем число внутри отрезка
return (r + l) / 2
В данном случае асимптотика будет равна ввиду того, что мы неявно разбиваем отрезок на частей и ищем уже отрезок, который максимально подходит под условие задачи.