Бинарный поиск - Алгоритмика

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