C++ Course
  • Описание курса
  • Материалы лекций
  • Задания
  • Об авторе
  • Гайды

On this page

  • Бинарный поиск
    • В отсортированном массиве
      • Проверка свойств
  • Бинарный поиск по ответу
    • «Коровы в стойла»
    • «Принтеры»
    • Бинарный поиск с вещественными аргументами

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

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

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

  • Игра в “данетку” или как можно красиво определить загаданное число от 1 до 100

    Задача. Загадано целое число \(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\)).

    Вот пример такой программы, которую можно запустить в консоли:

    #include <iostream>
    #include <string>
    
    int main() {
        int l = 1, r = 100;
    
        while (l <= r) {
            int m = (l + r) / 2;
            std::string resp;
            std::cout << "x > " << m << "? ";
            std::cin >> resp;
    
            if (resp == "yes") {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
    
        std::cout << "x = " << l << std::endl;
        return 0;
    }

    Если загадать \(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\). И если такой элемент есть, то определить его индекс. Очевидное решение потребует перебора всех элементов и будет иметь линейную сложность. Теперь предложим более оптимальный алгоритм – алгоритм бинарного поиска, который будет иметь логарифмическую сложность, то есть \({\cal{O}(\log n)}\)

  1. зададим левую и правую границу области поиска: \(l := 0, r := n\). Изначально рассматриваем все элемента массива

  2. Массив отсортирован в порядке возрастания элементов

  3. Посмотрим на элемент в середине массива, то есть находящийся по индексу \(m := \frac{l + r}{2}\)

  4. Если элемент в середине области поиска меньше искомого, то тогда искомый элемент находится левее середины массива, то есть в правой половине области поиска. Более формально, \(a[m] < x \Rightarrow x \in \Big\{ a[m + 1], a[m + 2], \dots, a[r] \Big\}\). Чтобы выбрать для следующего шага правую половину области поиска, достаточно сдвинуть левую границу в середину: \(l = m\)

  5. Аналогично, если же элемент в середине области поиска больше искомого, то искомый находится в левой половине. В этом случае двигаем правую границу в середину \(r = m\)

  6. Возвращаемся в шаг 3 до сходимости. Сходимость границ – когда левая граница становится больше правой или когда разница между ними становится равно единицы. Конкретное условие зависит от того, как именно вы сдвигаете границы поиска.

Ниже приведена функция, которая реализует поиск в отсортированном массиве чисел.

#include <vector>
#include <iostream>

int find(const std::vector<int>& data, int elem_to_find) {
    int n = static_cast<int>(data.size());
    int l = 0, r = n;

    while (l <= r) {
        int m = (l + r) / 2;
        if (data[m] == elem_to_find) {
            return m;
        }
        else if (data[m] < elem_to_find) {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    return -1;
}

int main() {
    std::vector<int> data = {1, 2, 3, 4, 5};
    int elem_to_find;
    std::cin >> elem_to_find;
    int result = find(data, elem_to_find);
    std::cout << "Result: " << result << std::endl;

    return result;
}

Для стандартных контейнеров 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\) раз запустить бинарный поиск.


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

В этой статье на примере нескольких задач мы рассмотрим важную разновидность бинарного поиска — бинарный поиск по ответу — заключающийся в том, чтобы сформулировать задачу как «найдите максимальное \(x\) такое, что такое-то легко вычислимое свойство от \(x\) выполняется» и найти этот \(x\) бинпоиском.

«Коровы в стойла»

На прямой расположены \(n\) стойл (даны их координаты на прямой), в которые необходимо расставить \(k\) коров так, чтобы минимальное расстояние между коровами было как можно больше.

Гарантируется, что \(1 < k < n\).

Если решать задачу в лоб, то вообще неясно, что делать. Вместо этого нужно решим более простую задачу: предположим, что мы знаем это расстояние \(x\), ближе которого коров ставить нельзя. Тогда сможем ли мы расставить самих коров?

Ответ — да, причём довольно просто: самую первую ставим в самое левое стойло, потому что это всегда выгодно. Следующие несколько стойл надо оставить пустыми, если они на расстоянии меньше \(x\), а в самое левое стойло из оставшихся надо поставить вторую корову, и так далее.

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

bool check(int x) {
    int cows = 1;
    int last_cow = coords[0];
    for (int c : coords) {
        if (c - last_cow >= x) {
            cows++;
            last_cow = c;
        }
    }
    return cows >= k;
}

Если в конце такого жадного алгоритма коровы у нас кончились раньше, чем безопасные стойла, то ответ точно не меньше \(x\), а если у нас не получилось, то ответ точно меньше \(x\).

Теперь мы можем перебрать \(x\) и сделать \(X = \frac{\max x_i - \min x_i}{k}\) проверок за \(O(n)\), но можно и ещё быстрее.

Запустим бинпоиск по \(x\) — ведь для каких-то маленьких \(x\) коров точно можно расставить, а начиная с каких-то больших — уже нельзя, и как раз это границу нас и просят найти в задаче.

int solve() {
    sort(coords.begin(), coords.end());
    int l = 0; // так как коров меньше, чем стойл, x = 0 нам всегда хватит
    // по условию есть хотя бы 2 коровы,
    // которых мы в лучшем случае отправим в противоположные стойла:
    int r = coords.back() - coords[0] + 1;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (check(m))
            l = m;
        else
            r = m;
    }
    return l;
}

Каждая проверка у нас работает за \(O(n)\), а внешний бинпоиск — за \(O(\log n)\) проверок, так что асимптотика будет \(O(n \log X)\).

«Принтеры»

Есть два принтера. Один печатает лист раз в \(x\) минут, другой раз в \(y\) минут. За сколько минут они напечатают \(n\) листов?

\(n > 0\)

Здесь, в отличие от предыдущей задачи, кажется, существует прямое решение с формулой. Но вместо того, чтобы о нем думать, можно просто свести задачу к обратной. Давайте подумаем, как по числу минут \(t\) (ответу) понять, сколько листов напечатается за это время? Очень легко:

\(\left \lfloor \frac{t}{x} \right \rfloor + \left \lfloor \frac{t}{y} \right \rfloor\)

Ясно, что за \(0\) минут \(n\) листов распечатать нельзя, а за \(x \cdot n\) минут один только первый принтер успеет напечатать \(n\) листов. Поэтому \(0\) и \(xn\) — это подходящие изначальные границы для бинарного поиска.

#include <iostream>
#include <string>

int main() {
    int l = 1, r = 100;

    while (l <= r) {
        int m = (l + r) / 2;
        std::string resp;
        std::cout << "x > " << m << "? ";
        std::cin >> resp;

        if (resp == "yes") {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }

    std::cout << "x = " << l << std::endl;
    return 0;
}

Аналогичными рассуждениями решаются задачи “Дипломы” и “Веревочки”.

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

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

Denis Bakin ©

Build on Quart Academic Website Template adapted by Dr. Gang He