binary-search.md

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

Пусть дан отсортированный массив $a$, и требуется определить, есть ли в нём элемент $x$.

Чтобы это сделать, не обязательно даже тратить $O(n)$ операций на просмотр всех элементов массива. Можно воспользоваться следующим методом.

Пример. Пусть автор загадал число $x$ от $1$ до $100$, которое вам нужно отгадать какой-нибудь «данеткой». Вам разрешено спрашивать, больше

Примечание. На самом деле, быстрее $O(\log n)$, а точнее $\lfloor \log n \rfloor$.

Однако иногда найти число X в массиве можно и быстрее! Для этого надо добавить условие на то, что массив отсортирован. Но давайте начнем не с этого.

Задание

Я загадал число X от 1 до 100. Вы можете спрашивать, больше ли мое число чем число T, я отвечаю "да" или "нет". За сколько вопросов в худшем случае вы сможете найти число X? Как нужно действовать?

Решение и состоит в идее бинарного (двоичного) поиска - нужно первым вопросом спросить "число X больше, чем 50?". После этого, если ответ "нет", надо спросить "число X больше, чем 25"? И так далее, нужно уменьшать отрезок возможных значений в два раза каждый раз.

Почему нужно делить обязательно пополам? Почему бы не спросить "число X больше, чем 80?" первым же вопросом? Но если вдруг ответ "нет", то мы останемся с 80 вариантами вместо 100. То есть деление отрезка ровно пополам гарантирует, что в худшем случае мы останемся не более чем с половиной вариантов.

Чтобы понять, как быстро это работает, введём новую математическую функцию. Логарифмом по основанию $a$ от $b$ будем называть число $c$, такое что $a ^ c = b$. Обозначается как $\log_a b = c$. Чаще всего мы будем работать с двоичным логарифмом, то есть в какую степень $c$ нужно возвести двойку, чтобы получить $b$. Поэтому договоримся, что запись $\log n$ означает двочный логарифм $n$.

Теперь вернёмся к нашей задаче. Можно понять, что такой алгоритм работает как раз за $O(\log n)$ вопросов (если число 100 на заменить абстрактную переменную $n$). Несложно убедиться, что именно логарифм раз нужно поделить число на два, чтобы получилось 1.

Общий принцип

А теперь представьте такую задачу: у вас есть массив, состоящий из некоторого количества подряд идущих нулей, за которыми следует какое-то количество подряд идущих единиц.

a = [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
n = len(a)
n

14

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

Давайте обратимся к идее бинарного поиска. Посмотрим на элемент посередине массива. Если это нуль, то первую единицу стоит искать в правой половину массива, а если единица - то в левой.

Есть много способов писать бинарный поиск, и в его написании люди очень часто путаются. Очень удобно в данном случае воспользоваться инвариантом (это слово значит "постоянное свойство"):

Пусть переменная left всегда указывает на $0$ в массиве, а переменная right всегда указывает на $1$ в массиве.

Дальше мы будем переменные left и right постепенно сдвигать друг к другу, и в какой-то момент они станут соседними числами. Это и будет означать, что мы нашли место, где заканчиваются нули и начинаются единицы.

Чему равны left и right изначально, когда мы ничего про массив не знаем? Первая приходящая в голову идея - поставить их на $0$ и $n-1$ соответственно. Увы, в общем случае это может быть неверно, потому что 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

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

Например, если мы хотим найти, есть ли число $X$ в отсортированном массиве, то мы просто представим, что $0$ - это числа, меньшие $X$, а $1$ - это числа, большие или равные $X$. Тогда достаточно найти первую "единицу" и проверить, равно ли это число $X$.

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 в отсортированном массиве (в решении помогают два предыдущих пункта)
• Дан массив чисел, первая часть состоит из нечетных чисел, а вторая - из четных. Найти индекс, начиная с которого все числа четные.

Все эти задачи решаются бинарным поиском за $O(\log{n})$. Правда нужно понимать, что в чистом виде такую задачу решать двоичным поиском бессмысленно - ведь чтобы создать массив размера $n$, уже необходимо потратить $O(n)$ операций.

Поэтому зачастую такие задачи сформулированы таким образом:

Дан отсортированный массив размера $n$. Нужно ответить на $m$ запросов вида "встречается ли число $x_i$ в массиве n"?

Задание

Найдите время работы, за которое решается эта задача?

.

.

.

.

.

.

.

.

.

.

Решение: Такая задача решается за $O(n + m\log{n})$ - нужно создать массив за $O(n)$ и $m$ раз запустить бинарный поиск.

Задание

Решите 3 первые задачи в этом контесте:

https://informatics.msk.ru/moodle/mod/statements/view.php?id=33216

Бинарный поиск с вещественными числами

У нас все еще есть функция f(x), которая сначала равна 0, а потом равна 1, и мы хотим найти это место, где она меняет значение. Но теперь аргумент функции - вещественное число. Например:

• $f(x) = 1$, если $x^2 > 2$
• $f(x) = 0$, если $x^2 \leq 2$

Понятно, что при $x = \sqrt 2$ $f(x) = 0$, а при любом даже немного большем значении $f(x) = 1$. Если мы научимся решать такую задачу, то мы научимся находить корень из двух!

Увы, возникает проблема: действительные числа хранятся в компьютере неточно

# известный пример
0.1 + 0.1 + 0.1

0.30000000000000004

Тем более не сможем найти точное значение $\sqrt 2$, потому что это бесконечная непериодическая дробь. Так что давайте снова воспользуемся бинарным поиском, причем всегда $f(left) = 0$, $f(right) = 1$, и мы остановимся тогда, когда left и right будет очень-очень близко.

И тут снова возникает проблема. Помимо того, что бесконечную дробь в принципе невозможно точно хранить в компьютере, ещё и арифметические операции понижают эту точность. Поэтому, чтобы явно не использовать разность между правым и левым указателем, можно задать фиксированное число шагов, которое будет выполняться.

Так как мы знаем, что двоичный поиск работает за двоичный логарифм, можно сказать, что на угадывание десятичного разряда числа потребуется примерно три шага бинпоиска (т. к. $\log 10 \approx 3 $). Значит, например, если нам нужно посчитать значение функции до шести знаков после запятой, то нам нужно ещё примерно 18 шагов уже после того, как расстояние между 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 с достаточно высокой точностью.

На самом деле, так можно искать ноль любой непрерывной функции (мы сейчас искали ноль функции $x^2 - 2$), у которой вы знаете значение меньше нуля и значение больше нуля.

Задание

Придумайте, как с помощью вещественного бинпоиска найти

• $\sqrt[\leftroot{-2}\uproot{2}17]{1000}$
• какой-нибудь корень уравнения $x^4 + 3x = 5$

Поиск максимума выпуклой функции: тернарный поиск, бинарный поиск

Так мы только что научились находить корень непрерывной функции, у которой мы знаем значение меньше и больше 0. Но можно ли найти с помощью бинарного поиска локальный максимум функции? Можно!

Как известно, локальный максимум функции $f$ - это просто такое $x_0$, что для всех близких к нему $x$ значения $f(x) < f(x_0)$. Для непрерывных функций выполняется более крутая вещь: слева от максимума функция возрастает, а справа от максимума функция убывает. Так это как раз отличное условие для нашего вещественного бинарного поиска!

Если вы знаете $x_1$ такое, что в его окрестности f(x) возрастает, и $x_2$ такое, что в его окрестности f(x) убывает, то можно запустить между ними бинпоиск и найти точку $x_0$ такую, что слева от нее возрастает значение функции, а справа - убывает. Это и есть локальный максимум.

А если функция выпуклая, то она вообще выглядит красиво: сначала возрастает, потом максимум, потом убывает.

Проблема только в одном: как по точке понять, в ее окрестности значение функции убывает или возрастает? Достаточно тыкнуть две точки очень-очень рядом с ней и сравнить их значения!

Задание

Придумайте, как с помощью вещественного бинпоиска найти

• максимум функции $x - e^x$ (она выпуклая, и максимум ровно один)
• какой-нибудь локальный максимум функции $31x+x^3-x^4$

Тернарный поиск

Другой способ искать максимум - это тернарный поиск. Пусть известно, что максимум находится между 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. После этого бинарным поиском мы таким же способом найдем пару соседних нуля и единицы в массиве.

Поэтому бинарный поиск работает и не для возрастающих массивов / функций, если наша задача состоит именно в поиске двух соседних индексов, в которых условие выполняется и не выполняется.

Например, если мы знаем, что $f(x_0) &lt; 0$ и $f(x_1) &gt; 0$, и функция непрерывная, то бинарным поиском можно найти ноль этой функции между $x_0$ и $x_1$, даже если функция не монотонная!

Или, например, если нужно в массиве найти соседние четное и нечетное числа, и известно положение какого-то четного числа и какого-то нечетного числа, то это тоже можно легко сделать с помощью бинарного поиска.

Полезно иметь это в виду, это применяется в нескольких задачах контестов.

Бинарный поиск по ответу

Рассмотрим такую задачу:

Пример: "Корова в стойла"

Условие: На прямой расположены N стойл (даны их координаты на прямой), в которые необходимо расставить K коров так, чтобы минимальное расcтояние между коровами было как можно больше. Гарантируется, что $1 &lt; K &lt; N$.

**Решение: **

Если решать задачу в лоб, то вообще неясно что делать. Нужно решать обратную задачу: давайте предположим, что мы знаем это расстояние 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 выполняется" и решили её бинпоиском. Самое сложное - увидеть такую формулировку в задаче. Поэтому рассмотрим еще один пример.

Пример: "Очень Легкая Задача"

Условие: есть два принтера, один печатает лист раз в $x$ минут, другой раз в $y$ минут. За сколько минут они напечатают $N$ листов? $N &gt; 0$

Решение: Здесь, в отличие от предыдущей задачи, кажется, существует прямое решение с формулой. Но вместо того, чтобы о нем думать, можно просто свести задачу к обратной. Давайте подумаем, как по числу минут $T$ (ответу) понять, сколько листов напечатается за это время? Очень легко: $$\lfloor\frac{T}{x}\rfloor + \lfloor\frac{T}{y}\rfloor$$

Ясно, что за $0$ минут $N$ листов распечатать нельзя, а за $xN$ минут один только первый принтер успеет напечатать $N$ листов. Поэтому $0$ и $xN$ - это подходящие первые границы для бинарного поиска.

Примечание: заметьте, что задача в контесте немного отличается! Прочитайте внимательно условие.

Задание

Решите как можно больше задач в практическом контесте:

https://informatics.msk.ru/mod/statements/view.php?id=34097

Там могут встречаться задачи как на бинпоиск по ответу, так и на тернарный поиск по ответу.