Определение

Пусть задана монотонная (возрастающая или убывающая) функция \(f(x)\), а также некоторое значение \(y\). Бинарный, или двоичный, поиск - алгоритм, позволяющий за время \(O(\log N)\) найти такое значение \(x\), что \(f(x) = y\).

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

Алгоритм

Бинарный поиск - один из самых простых и полезных алгоритмов. Его идея заключается в поддерживании некоторого промежутка значений \(x\), который точно содержит искомое значение, и постепенном его сужении до одного элемента (в случае поиска по массиву) или допустимой погрешности (в случае поиска по непрерывной функции).

Предположим, что наша функция возрастает, и текущие границы промежутка, точно содержащего \(x\), это \([l; r]\). Сужение выполняется следующим образом: возьмём “среднюю” точку в промежутке \(m = \frac{l + r}{2}\), и сравним \(f(m)\) с \(y\):

  • Если \(f(m) < y\), то для всех \(x < m\) правда, что \(f(x) \le f(m) < y\). То есть промежуток \([l; m)\) нас не интересует: \(x\) точно находится в \([m; r]\).
  • Если \(f(m) > y\), то по такой же логике промежуток \((m; r]\) нас не интересует, можем сузить диапазон поиска до \([l; m]\).
  • Если \(f(m) = y\), то мы нашли искомое значение: \(x = m\).

После каждого шага мы либо находим ответ, либо сужаем диапазон поиска в два раза. В случае поиска по непрерывной функции в какой-то момент длина отрезка \([l; r]\) станет меньше допустимой погрешности (например, \(10^{-6}\)), и любой из концов отрезка можно считать ответом. В случае поиска по массиву (где \(l\) и \(r\) должны быть целыми числами), в какой-то момент станет так, что \(l = r = x\), где \(x\) - индекс элемента \(y\), если он присутствует в массиве, или позиция в массиве, на которую можно вставить \(y\), не нарушая порядка сортировки.

Если функция не возрастает, а убывает, алгоритм выглядит практически так же, но логика при сужениях обратная: если \(f(m) < y\), то откидываем правую половину, и наоборот.

Стоит заметить, что иногда может существовать несколько значений \(x\), таких что \(f(x) = y\). Версия алгоритма, описанная выше, найдёт произвольное из всех допустимых \(x\). Часто нас интересует наименьшее (или наибольшее) из этих значений. Существует простейшая модификация алгоритма, решающая эту проблему, к которой мы ещё вернёмся позже.

Сложность алгоритма

Реализация для непрерывной функции на C++

Для этого примера в качестве функции будем использовать возведение в квадрат: \(f(x) = x^2\). Нам нужно для заданного \(y\) найти такое \(x\), что \(x^2 = y\). Можно заметить, что это есть не что иное, как квадратный корень из \(y\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

double binsearch_sqrt(double y) {
    double l = 0, r = 1e9;      //изначальные границы выбираются исходя из
                                //ограничений на данные в конкретной задаче

    while (r - l > 1e-6) {      //допустимая погрешность: 10^-6
        double m = (l + r) / 2;
        double cur = m * m;

        if (cur < y) {
            l = m;
        } else if (cur > y) {
            r = m;
        } else {
            return m;
        }
    }

    return l;   //l и r практически равны, поэтому неважно,
                //что из них считать ответом.
}

Реализация для отсортированного массива как дискретной функции на C++

Самый распространённый пример бинарного поиска по дискретной функции - поиск элемента в отсортированном массиве. Функцию можно записать в виде \(f(x) = a_x\), или \(f(x) = a[x]\), где \(a\) - отсортированный массив. Другими словами, бинарный поиск по массиву позволяет найти индекс элемента с заданным значением.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

int binsearch_array(vector<int>& a, int val) {
    int l = 0, r = a.size() - 1;

    while (r > l) {
        int m = (l + r) / 2;    //целочисленное деление!

        if (a[m] < val) {
            l = m + 1;
        } else if (a[m] > val) {
            r = m - 1;
        } else {
            return m;
        }
    }

    //l == r == искомый индекс

    //Если искомого элемента не было в массиве,
    //бинарный поиск найдёт следующий после него элемент.
    //Чтобы распознать этот случай, мы используем дополнительное сравнение.
    if (a[l] == val) {
        return l;
    } else {
        return -1;
    }
}

С дискретными функциями связано несколько тонких моментов, часто приводящих к ошибкам, вызывающим зацикливание алгоритма. А именно: возможность использования открытых или закрытых границ (включающих или исключающих элементы \(L\) и \(R\)), и целочисленного деления на два при поиске среднего элемента. Чтобы избежать ошибок, нужно следовать одному простому правилу: новые границы всегда должны включать элемент \(M + 1\) или \(M - 1\), но не включать элемент \(M\). При выполнении этого условия бинарный поиск будет работать корректно.

Реализации бинарного поиска в стандартной библиотеке C++

В стандартной библиотеке C++ содержатся две основные функции реализующие бинарный поиск на отсортированном массиве. Их определения:

//параметр value должен иметь тип, на который указывают итераторы.

//возвращает итератор на первый элемент, больший либо равный value
iterator std::lower_bound(iterator begin, iterator end, int value);

//возвращает итератор на первый элемент, строго больший value
iterator std::upper_bound(iterator begin, iterator end, int value);

Обе эти функции предполагают, что отрезок \([begin;end)\) отсортирован по стандартному компаратору, в противном случае их поведение не определено. Для нахождения самого элемента обычно используется функция std::lower_bound. При наличии элемента, она вернёт итератор на него, а при отсутствии - на следующий в порядке сортировки. Если value больше всех элементов промежутка, функция вернёт итератор end.

Функция std::upper_bound используется в особых ситуациях, когда нужно найти положение первого элемента, больше заданного.

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

\[[lower\_bound(x); upper\_bound(x))\]

Для бинарного поиска по массиву, отсортированному по собственному компаратору вы можете воспользоваться расширенной формой функций:

iterator lower_bound(iterator begin, iterator end, int value, comparator comp);
iterator upper_bound(iterator begin, iterator end, int value, comparator comp);

Вы также можете осуществлять бинарный поиск по библиотечным классам std::set и std::map. Для этого используйте методы классов:

set<int> s;
// ...
set<int>::iterator it = s.lower_bound(k);

map<int, string> m;
// ...

// бинарный поиск для std::map ведётся по ключам
map<int, string>::iterator it = m.lower_bound(k);

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

Бинарный поиск по ответу - распространённый подход при решении задач. Часто применяется в задачах и подзадачах вида “найдите максимально возможное количество чего-либо при котором выполняются определённые условия”. Бинарный поиск по ответу в таких задачах можно применять, когда выполняются следующие условия:

  • Если возможен ответ \(N\), то гарантированно возможен и ответ \(N − 1\).
  • Если невозможен ответ \(N\), то гарантированно невозможен и ответ \(N + 1\).

В качестве примера рассмотрим следующую задачу: CF 218 Div2 C. Гамбургеры Параметр, по которому мы выполняем бинарный поиск - количество гамбургеров, которые Поликарп может приготовить. Реализуем соотвествующие функции:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

//Считаем, что входные данные уже введены.
long long nb, ns, nc;
long long pb, ps, pc;
long long r;

//Количество необходимых кусков хлеба, колбасы и сыра для одного гамбургера.
//Рассчитывается из строки рецепта.
long long tb, ts, tc;

//Возможно ли приготовить h гамбургеров.
bool possible(long long h) {
    long long cost_b = max(0ll, (tb * h - nb) * pb);
    long long cost_s = max(0ll, (ts * h - ns) * ps);
    long long cost_c = max(0ll, (tc * h - nc) * pc);

    return cost_b + cost_s + cost_c <= r;
}

//Можно заметить, что это не стандартный бинарный поиск
//по элементу, а поиск первого "невозможного" количества
//гамбургеров (аналог std::upper_bound).
//В реализации таких функций часто допускаются ошибки
//в строках подобных 32 и 34, но они быстро выявляются и
//исправляются тестированием на сэмплах.
long long max_possible() {
    long long l = 0, r = 1e14;

    while (l < r) {
        long long m = (l + r) / 2;

        if (possible(m)) {
            l = m + 1;
        } else {
            r = m;
        }
    }

    return l - 1;   //l == r == первое "невозможное" количество
}

Полное решение этой задачи.