Задача. Загадано целое число $x$ от $1$ до $100$, которое вам нужно отгадать какой-нибудь «данеткой»: например, вы можете спрашивать, больше ли число $x$ чем заданное, или четно ли оно. За сколько вопросов в худшем случае вы сможете найти число $x$?
Одно из оптимальных решений имеет такую структуру: первым вопросом спрашиваем «больше ли число $x$, чем 50», и если ответ «да», то дальше спрашиваем «больше ли число $x$, чем 75», иначе «больше ли число $x$, чем 25», и повторяем дальше, каждый раз уменьшая отрезок возможных значений в два (или почти в два) раза.
Более структурно, если у нас есть отрезок поиска — изначально от $l=1$ до $r=100$ — то мы на каждой итерации выбираем «серединный» элемент $m = \lfloor \frac{l+r}{2} \rfloor$, спрашиваем «$x>m?$», выполняем присвоения $l = m + 1$ или $r = m$ в зависимости от ответа, и повторяем процедуру с новыми границами, пока они не станут равными (что будет означать, что $l = r = x$).
Вот пример такой программы, которую можно запустить в консоли:
l, r = 1, 100
while l < r:
m = (l + r) // 2
resp = input(f'x > {m}? ')
if resp == 'yes':
l = m + 1
else:
r = m
print(f'x = {l}')
Если загадать $x=42$ и честно поотвечать на вопросы:
x > 50? no
x > 25? yes
x > 38? yes
x > 44? no
x > 41? yes
x > 43? no
x > 42? no
x = 42
Здесь нам потребовалось 7 вопросов, но в зависимости от загаданного числа иногда мы будем спрашивать ровно $7$ вопросов, а иногда $6$.
В общем случае, так как на каждой итерации длина отрезка поиска гарантированно уменьшится в два раза (возможно, с округлением вверх), то нам потребуется $O(\log n)$ операций, а точнее либо $\lceil \log_2 n \rceil$, либо $\lfloor \log_2 n \rfloor$.
#В структурах данных
Пусть дан массив $a$, и требуется определить, есть ли в нём элемент $x$.
Очевидно, в худшем случае этого элемента в массиве нет, но чтобы удостовериться в этом, нужно потратить $O(n)$ операций на просмотр всех элементов массива.
Однако, если массив отсортирован, найти число $x$ в массиве можно и быстрее: можно аналогичным способом найти нижнюю грань (англ. lower bound) — самое малое число, не меньшее $x$ — и проверить, оказалось ли оно равно $x$.
bool find(int x, int *a, int n) {
int l = 0, r = n + 1;
// отрезок поиска теперь полуинтервал: [l, r)
while (l + 1 < r) {
int m = (l + r) / 2;
if (a[m] >= x)
l = m;
else
r = m;
}
return (l < n && a[l] == x);
}
Для стандартных контейнеров STL такая функция реализована:
bool find(x, vector<int> a) {
auto it = lower_bound(a.begin(), a.end(), x);
return (it != a.end() && *it == x);
}
Также в C++ есть функция upper_bound, которая находит первый элемент, который строго больше аргумента.
#Проверка свойств
Подобный метод обобщается не только на поиск элементов, но и на проверку каких-либо монотонных свойств, которые сначала выполняются, а потом не выполняются, или наоборот.
Поиск нижней границы в массиве — частный случай: мы проверяем условие $(a[k] \geq x)$ и хотим найти, начиная с какого $k$ оно выполняется.
Другие примеры:
- Найти последнее число, равное $x$ в отсортированном массиве, или вывести, что таких чисел нет.
- Посчитать, сколько раз встречается число $x$ в отсортированном массиве.
- Дан массив чисел, первая часть состоит из нечетных чисел, а вторая из четных. Найти индекс, начиная с которого все числа четные.
Все эти задачи решаются бинарным поиском за $O(\log{n})$. Правда нужно понимать, что в чистом виде такую задачу решать двоичным поиском бессмысленно — ведь чтобы создать массив размера $n$, уже необходимо потратить $O(n)$ операций.
Поэтому зачастую такие задачи сформулированы таким образом: дан отсортированный массив размера $n$. Нужно ответить на $m$ запросов вида «встречается ли число $x_i$ в массиве?». Подобные задача решается за $O(n + m\log{n})$ — нужно сначала создать массив за $O(n)$ и $m$ раз запустить бинарный поиск.
#Бинарный поиск с вещественными аргументами
У нас все еще есть функция-предикат $f(x)$, которая сначала равна нулю, а потом единице, и мы хотим найти это место, где она меняет значение. Но теперь аргумент функции — вещественное число.
Пример такой функции:
$$ f(x) = \begin{cases} 0, & x^2 < 2 \\ 1, & x^2 \geq 2 \end{cases} $$При $x < \sqrt 2$, $f(x) = 0$, а при сколько-либо большем значении $f(x) = 1$. Если мы научимся находить такое $x_0$, что $f(x_0) = 0$ и $f(x_0 + \epsilon) = 1$ для какого-то малого $\epsilon$, то мы научимся считать корень из двух — и любого другого положительного числа.
Мы можем так же применить здесь бинарный поиск, но увы, возникает проблема: действительные числа хранятся в компьютере неточно.
# известный пример
print(0.1 + 0.1 + 0.1)
# = 0.30000000000000004
Тем более не сможем найти точное значение $\sqrt 2$, потому что это бесконечная непериодическая дробь.
Так что при реализации бинарного поиска с вещественными аргументами нужно действовать осторожно:
- Нужно убедиться, что $f(l_0) = 0$ и $f(r_0) = 1$.
- Нужно либо останавливаться, когда $r - l < \epsilon$, либо (лучше) делать фиксированное число итераций.
Сколько итераций понадобится, чтобы получить $k$ правильных цифр? Так как двоичный поиск работает за двоичный логарифм, можно сказать, что на угадывание десятичного разряда числа потребуется примерно три шага бинпоиска ($\log 10 \approx 3$). Значит, если нам, например, нужно посчитать значение функции до шести знаков после запятой, то нам нужно ещё примерно 18 шагов уже после того, как расстояние между $l$ и $r$ достигло одного.
Чтобы каждый раз об этом не думать, можно считать, что ста шагов бинпоиска всегда хватит для всех разумных целей:
float sqrt(float x) {
float l = 0, r = x;
for (int i = 0; i < 100; i++) {
float m = (l + r) / 2;
if (m * m < x)
l = m;
else
r = m;
}
return l;
}
На самом деле, так можно искать ноль любой непрерывной функции (мы сейчас искали ноль функции $x^2 - 2$), у которой известны значения аргумента, при которых она принимает значения меньше нуля и больше нуля.