Пусть дан отсортированный массив
Чтобы это сделать, не обязательно даже тратить
Пример. Пусть автор загадал число
Примечание. На самом деле, быстрее
Однако иногда найти число X в массиве можно и быстрее! Для этого надо добавить условие на то, что массив отсортирован. Но давайте начнем не с этого.
Я загадал число X от 1 до 100. Вы можете спрашивать, больше ли мое число чем число T, я отвечаю "да" или "нет". За сколько вопросов в худшем случае вы сможете найти число X? Как нужно действовать?
Решение и состоит в идее бинарного (двоичного) поиска - нужно первым вопросом спросить "число X больше, чем 50?". После этого, если ответ "нет", надо спросить "число X больше, чем 25"? И так далее, нужно уменьшать отрезок возможных значений в два раза каждый раз.
Почему нужно делить обязательно пополам? Почему бы не спросить "число X больше, чем 80?" первым же вопросом? Но если вдруг ответ "нет", то мы останемся с 80 вариантами вместо 100. То есть деление отрезка ровно пополам гарантирует, что в худшем случае мы останемся не более чем с половиной вариантов.
Чтобы понять, как быстро это работает, введём новую математическую функцию. Логарифмом по основанию
Теперь вернёмся к нашей задаче. Можно понять, что такой алгоритм работает как раз за
А теперь представьте такую задачу: у вас есть массив, состоящий из некоторого количества подряд идущих нулей, за которыми следует какое-то количество подряд идущих единиц.
a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
n = len(a)
n
14
Вам дан массив, и вам нужно найти позицию первой единицы, то есть найти такое место, где заканчиваются нули, и начинаются единицы. Это можно сделать с помощью линейного поиска за один проход по массиву, но хочется сделать это быстрее.
Давайте обратимся к идее бинарного поиска. Посмотрим на элемент посередине массива. Если это нуль, то первую единицу стоит искать в правой половину массива, а если единица - то в левой.
Есть много способов писать бинарный поиск, и в его написании люди очень часто путаются. Очень удобно в данном случае воспользоваться инвариантом (это слово значит "постоянное свойство"):
Пусть переменная left
всегда указывает на right
всегда указывает на
Дальше мы будем переменные left
и right
постепенно сдвигать друг к другу, и в какой-то момент они станут соседними числами. Это и будет означать, что мы нашли место, где заканчиваются нули и начинаются единицы.
Чему равны left
и right
изначально, когда мы ничего про массив не знаем? Первая приходящая в голову идея - поставить их на a[0]
может быть единицей, а a[n-1]
может быть нулём. Правильнее сделать вот так:
left = -1
right = n
То есть изначально left
и right
указывают на несуществующие индексы. Но это нормально - например в массиве [1, 1, 1, 1]
в конце алгоритма как раз должно быть left == -1
, right == 0
.
Осталось нам написать цикл while
:
while right - left > 1:
middle = (left + right) // 2 # именно такая формула для среднего индекса между left и right
if a[middle] == 1:
right = middle # right всегда должна указывать на 1
else:
left = middle # left всегда должна указывать на 0
print left, right
print a[left], a[right]
8 9
0 1
Мы решили задачу для ноликов и единичек, но это легко обобщается на абсолютно любую задачу, где есть какое-то свойство, которое в начале массива не выполняется, а потом выполняется.
Например, если мы хотим найти, есть ли число
a = [1, 3, 4, 10, 10, 10, 11, 80, 80, 81] # отсортированный массив
def bin_search(a, x):
n = len(a)
left = -1
right = n
while right - left > 1:
middle = (left + right) // 2
if a[middle] >= x: # практически единственная строка, которая меняется от задачи к задаче
right = middle
else:
left = middle
if right != n and a[right] == x: # ответ лежит в right
return True
else:
return False
print (bin_search(a, 1))
print (bin_search(a, 10))
print (bin_search(a, 20))
print (bin_search(a, 79))
print (bin_search(a, 80))
print (bin_search(a, 81)
True
True
False
False
True
True
Придумайте, как с помощью бинарного поиска решить такие задачи:
- Найти первое число, равное X в отсортированном массиве, или вывести, что таких чисел нет
- Найти последнее число, равное X в отсортированном массиве, или вывести, что таких чисел нет
- Посчитать, сколько раз встречается число X в отсортированном массиве (в решении помогают два предыдущих пункта)
- Дан массив чисел, первая часть состоит из нечетных чисел, а вторая - из четных. Найти индекс, начиная с которого все числа четные.
Все эти задачи решаются бинарным поиском за
Поэтому зачастую такие задачи сформулированы таким образом:
Дан отсортированный массив размера
Найдите время работы, за которое решается эта задача?
.
.
.
.
.
.
.
.
.
.
Решение: Такая задача решается за
Решите 3 первые задачи в этом контесте:
https://informatics.msk.ru/moodle/mod/statements/view.php?id=33216
У нас все еще есть функция f(x), которая сначала равна 0, а потом равна 1, и мы хотим найти это место, где она меняет значение. Но теперь аргумент функции - вещественное число. Например:
-
, если -
, если
Понятно, что при
Увы, возникает проблема: действительные числа хранятся в компьютере неточно
# известный пример
0.1 + 0.1 + 0.1
0.30000000000000004
Тем более не сможем найти точное значение left
и right
будет очень-очень близко.
И тут снова возникает проблема. Помимо того, что бесконечную дробь в принципе невозможно точно хранить в компьютере, ещё и арифметические операции понижают эту точность. Поэтому, чтобы явно не использовать разность между правым и левым указателем, можно задать фиксированное число шагов, которое будет выполняться.
Так как мы знаем, что двоичный поиск работает за двоичный логарифм, можно сказать, что на угадывание десятичного разряда числа потребуется примерно три шага бинпоиска (т. к. left
и right
достигло одного.
Чтобы каждый раз об этом не думать, можно считать, что ста шагов бинпоиска хватит для почти любых разумных целей.
left = 0.0 # 0^2 < 2, а значит f(0) = 0
right = 10.0 # 10^2 > 2, а значит f(10) = 1
for i in range(100):
middle = (left + right) / 2 # теперь деление не нацело, а вещественное
if middle ** 2 > 2:
right = middle # right всегда должна указывать на 1
else:
left = middle # left всегда должна указывать на 0
print left, right
print left ** 2, right ** 2
1.41421356237 1.41421356237
2.0 2.0
Вот мы и нашли корень из 2 с достаточно высокой точностью.
На самом деле, так можно искать ноль любой непрерывной функции (мы сейчас искали ноль функции
Придумайте, как с помощью вещественного бинпоиска найти
- какой-нибудь корень уравнения
Так мы только что научились находить корень непрерывной функции, у которой мы знаем значение меньше и больше 0. Но можно ли найти с помощью бинарного поиска локальный максимум функции? Можно!
Как известно, локальный максимум функции
Если вы знаете
А если функция выпуклая, то она вообще выглядит красиво: сначала возрастает, потом максимум, потом убывает.
Проблема только в одном: как по точке понять, в ее окрестности значение функции убывает или возрастает? Достаточно тыкнуть две точки очень-очень рядом с ней и сравнить их значения!
Придумайте, как с помощью вещественного бинпоиска найти
- максимум функции
(она выпуклая, и максимум ровно один) - какой-нибудь локальный максимум функции
Другой способ искать максимум - это тернарный поиск. Пусть известно, что максимум находится между left и right. Поделим отрезок на три равные части:
- middle_left = (2 * left + right) / 3
- middle_right = (left + 2 * right) / 3
Тогда если f(middle_left) < f(middle_right), то можно спокойно заменить left на middle_left (максимум точно не левее middle_left), а если f(middle_left) > f(middle_right), то можно спокойно заменить right на middle_right. Он будет работать не за двоичный логарифм, а за логарифм по основанию полтора, что больше (но асимптотически то же самое, так как отличается в константу раз).
Оба способа работают быстро, и обобщаются на дискретный случай (то, что было в начале - когда дан массив, значения в котором сначала возрастают, а потом убывают). Но проблема есть в том, что если функция нестрого возрастает и нестрого убывает, а именно если там есть отрезки постоянства, то алгоритм не работает. В случае, когда значения функции равны, никак нельзя понять, с какой стороны искать максимум - он может быть с любой стороны.
Решите 4 и 5 задачи в этом контесте:
https://informatics.msk.ru/moodle/mod/statements/view.php?id=33216
Заметьте, что в первоначальной задаче условие на то, что сначала идут нули, а потом идут единицы несущественно. Главное, чтобы мы знали индекс, который показывает на 0, и индекс, который показывает на 1. После этого бинарным поиском мы таким же способом найдем пару соседних нуля и единицы в массиве.
Поэтому бинарный поиск работает и не для возрастающих массивов / функций, если наша задача состоит именно в поиске двух соседних индексов, в которых условие выполняется и не выполняется.
Например, если мы знаем, что
Или, например, если нужно в массиве найти соседние четное и нечетное числа, и известно положение какого-то четного числа и какого-то нечетного числа, то это тоже можно легко сделать с помощью бинарного поиска.
Полезно иметь это в виду, это применяется в нескольких задачах контестов.
Рассмотрим такую задачу:
Условие: На прямой расположены N стойл (даны их координаты на прямой), в которые необходимо расставить K коров так, чтобы минимальное расcтояние между коровами было как можно больше. Гарантируется, что
**Решение: **
Если решать задачу в лоб, то вообще неясно что делать. Нужно решать обратную задачу: давайте предположим, что мы знаем это расстояние X, ближе которого коров ставить нельзя. Тогда сможем ли мы расставить самих коров?
Ответ - да, можно ставить их довольно просто: самую первую ставим в самое левое стойло, это всегда выгодно. Следующие несколько стойл надо оставить пустыми, если они на расстоянии меньше X. В самое левое стойло из оставшихся надо поставить вторую корову и так далее. Даже ясно как это писать: надо идти слева направо по отсортированному массиву стойл, хранить координату последней коровы, и либо пропускать стойло, либо ставить в него новую корову.
То есть если мы знаем расстояние X, то мы можем за O(n) проверить, можно ли расставить K коров на таком расстоянии. Ну так давайте запустим бинпоиск по X, ведь при слишком маленьком X коров точно можно расставить, а при слишком большом - нельзя, и как раз эту границу и просят найти в задаче ("как можно больше").
Осталось точно определить границы, то есть изначальные значения left и right. Нам точно хватит расстояния 0, так как гарантируется, что коров меньше, чем стойл. И точно не хватит расстояния max_coord - min_coord + 1, так как по условию есть хотя бы 2 коровы.
coords = [2, 5, 7, 11, 15, 20] # координаты стойл
k = 3 # число коров
def is_correct(x): # проверяем, можно ли поставить K коров в стойла, если между коровами расстояние хотя бы x
cows = 1
last_cow = coords[0]
for c in coords:
if c - last_cow >= x:
cows += 1
last_cow = c
return cows >= k
left = 0 # расставить коров на расстоянии хотя бы 0 можно всегда
right = max(coords) - min(coords) + 1 # при таком расстоянии даже 2 коровы поставить нельзя
while right - left != 1:
middle = (left + right) // 2
if is_correct(middle): # проверяем, можно ли поставить K коров в стойла, если между коровами расстояние хотя бы middle
left = middle # left всегда должна указывать на ситуацию, когда можно поставить коров
else:
right = middle # right всегда должна указывать на ситуацию, когда нельзя поставить коров
print left # left - максимальное расстояние, на котором можно расставить коров в стойла
9
Такой метод и называется бинпоиск по ответу. Он очень важный и очень распространен на олимпиадах, очень рекомендую решать на него задачи.
По сути мы просто взяли задачу "найдите максимальное X, такое что какое-то свойство от X выполняется" и решили её бинпоиском. Самое сложное - увидеть такую формулировку в задаче. Поэтому рассмотрим еще один пример.
Условие: есть два принтера, один печатает лист раз в
Решение:
Здесь, в отличие от предыдущей задачи, кажется, существует прямое решение с формулой. Но вместо того, чтобы о нем думать, можно просто свести задачу к обратной. Давайте подумаем, как по числу минут
Ясно, что за
Примечание: заметьте, что задача в контесте немного отличается! Прочитайте внимательно условие.
Решите как можно больше задач в практическом контесте:
https://informatics.msk.ru/mod/statements/view.php?id=34097
Там могут встречаться задачи как на бинпоиск по ответу, так и на тернарный поиск по ответу.