Определение

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

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

Алгоритм

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

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

  • Если , то для всех правда, что . То есть промежуток нас не интересует: точно находится в .
  • Если , то по такой же логике промежуток нас не интересует, можем сузить диапазон поиска до .
  • Если , то мы нашли искомое значение: .

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

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

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

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

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

Для этого примера в качестве функции будем использовать возведение в квадрат: . Нам нужно для заданного найти такое , что . Можно заметить, что это есть не что иное, как квадратный корень из .

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++

Самый распространённый пример бинарного поиска по дискретной функции - поиск элемента в отсортированном массиве. Функцию можно записать в виде , или , где - отсортированный массив. Другими словами, бинарный поиск по массиву позволяет найти индекс элемента с заданным значением.

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;
    }
}

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

Реализации бинарного поиска в стандартной библиотеке 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);

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

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

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

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

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);     

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

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

  • Если возможен ответ , то гарантированно возможен и ответ .
  • Если невозможен ответ , то гарантированно невозможен и ответ .

В качестве примера рассмотрим следующую задачу: 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 == первое "невозможное" количество
}

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