Бинарный поиск
Определение
Пусть задана монотонная (возрастающая или убывающая) функция \(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 == первое "невозможное" количество
}