Казалось бы, по бинпоиску написано столько материалов, что все должны знать, как писать его, однако в каждом материале похоже рассказывается свой подход, и я вижу, что люди теряются и допускают ошибки в такой простой штуке. Поэтому я хочу рассказать о подходе, который нахожу наиболее элегантным. Из всего многообразия статей, я увидел свой подход только в этом комментарии (но менее обобщённый).
Проблема
Предположим, вы хотите найти последний элемент в отсортированном массиве, меньший x
, и просто храните отрезок кандидатов на ответ [l, r]
. Если вы напишете:
int l = 0, r = n - 1; // отрезок кандидатов
while (l < r) { // больше одного кандидата
int mid = (l + r) / 2;
if (a[mid] < x) {
l = mid;
} else {
r = mid - 1;
}
}
cout << l;
...вы наткнётесь на проблему: предположим, l = 3
, r = 4
, тогда mid = 3
. Если a[mid] < x
, вы попадёте в цикл (на следующей итерации отрезок будет снова [3, 4]
).
Ладно, это можно исправить округлением mid
вверх – mid = (l + r + 1) / 2
. Но есть ещё одна проблема: что если в массиве нет таких элементов? Нам потребуется дополнительная проверка на этот случай. В результате, мы получили довольно уродливый код, который тяжело обобщить.
Мой подход
Давайте обобщим нашу задачу. У нас есть утверждение о целом числе n
, которое истинно для целых чисел меньше некоторой границы, но потом всегда остаётся ложным как толькоn
превысит её. Мы хотим найти последнееn
, для которого утверждение истинно.
Прежде всего, мы будем использовать полуинтервалы вместо отрезков (одна граница включительная, другая – нет). Полуинтервалы вообще очень полезны, элегантны и общеприняты в программировании, я рекомендую использовать их по возможности. В этом случае мы выбираем некое маленькое l
, для которого мы знаем, что утверждение истинно и некое большое r
, для которого мы знаем, что оно ложно. Тогда диапазоном кандидатов будет [l, r)
.
Моим код для этой задачи было бы:
int l = -1, r = n; // полуинтервал [l, r) кандидатов
while (r - l > 1) { // больше одного кандидата
int mid = (l + r) / 2;
if (a[mid] < x) {
l = mid; // теперь это наибольшее, для которого мы знаем, что это истинно
} else {
r = mid; // теперь это наименьшее, для которого мы знаем, что это ложно
}
}
cout << l; // в конце остаётся диапозон [l, l + 1)
Бинпоиск будет проверять только числа строго между изначальными l
и r
. Это значит, что он никогда не проверит условие для l
и r
, он поверит вам, что для l
это истинно, а для r
– ложно. Здесь мы считаем -1
корректным ответом, который соответствует случаю, когда ни один элемент массива не меньше x
.
Заметьте, что у меня в коде нет "+ 1" или "- 1", и мне не нужны дополнительные проверки, и попадание в цикл невозможно (т. к. mid
строго между текущими l
и r
).
Обратная задача
Единственная вариация, которую вам надо держать в голове – это что в половине случаев вам нужно будет найти не последнее, а первое число, для которого нечто выполняется. В этом случае утверждение должно быть всегда ложно для меньших чисел и всегда истинно, начиная с некоторого числа.
Мы будем делать примерно то же самое, но теперьr
будет включительной границей, а l
– не включительной. Другими словами, l
теперь – некоторое число, для которого мы знаем, что утверждение ложно, а r
– некоторое, для которого мы знаем, что оно истинно. Предположим, я хочу найти первое число n
, для которогоn * (n + 1) >= x
(x
положительно):
int l = 0, r = x; // полуинтервал (l, r] кандидатов
while (r - l > 1) { // больше 1 кандидата
int mid = (l + r) / 2;
if (mid * (mid + 1) >= x) {
r = mid; // теперь это наименьшее, для которого мы знаем, что это истинно
} else {
l = mid; // теперь это наибольшее, для которого мы знаем, что это ложно
}
}
cout << r; // в конце остаётся диапозон (r - 1, r]
Только будьте осторожны с выбором r
, слишком большое может привести к переполнению.
Пример
1201C - Максимальная медиана Вам дан массив a
нечётной длины n
и за один шаг можно увеличить один элемент на 1. Какую наибольшую медиану массива можно достичь за k
шагов?
Рассмотрим утверждение о числе x
: мы можем сделать медиану не меньше x
за не более, чемk
шагов. Конечно, это всегда истинно до некоторого числа, а затем всегда ложно, поэтому можно использовать бинпоиск. Так как нам нужно последнее число, для которого это истинно, мы будем использовать обычный полуинтервал [l, r)
.
Чтобы проверить данное x
, мы можем воспользоваться свойством медианы. Медиана не меньше x
тогда и только тогда, когда не менее половины всех элементов не меньше x
. Конечно, оптимальным способом добиться этого будет взять наибольшую половину элементов и сделать их не меньше x
.
Конечно, можно достичь медиану не менее 1
при данных ограничениях, так что l
будет равно1
. Но даже если есть только один элемент, равный 1e9
и k
тоже равно1e9
, мы всё равно не сможем добиться медианы 2e9 + 1
, так что r
будет равно 2e9 + 1
. Реализация:
#define int int64_t
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
int l = 1, r = 2e9 + 1; // полуинтервал [l, r) кандидатов
while (r - l > 1) {
int mid = (l + r) / 2;
int cnt = 0; // необходимое количество шагов
for (int i = n / 2; i < n; i++) { // идём по наибольшей половине
if (a[i] < mid) {
cnt += mid - a[i];
}
}
if (cnt <= k) {
l = mid;
} else {
r = mid;
}
}
cout << l << endl;
Заключение
Надеюсь, я разъяснил кое-что, и часть из вас переключится на эту имплементацию. Для уточнения, иногда другие имплементации могут оказаться более подходящими, например, в интерактивных задачах – когда нам нужно мыслить в терминах интервала поиска, а не в терминах первого/последнего числа, для которого что-то выполняется.
Я напоминаю, что даю частные уроки по спортивному программированию, цена – $30/ч. Пишите мне в Telegram, Discord: rembocoder#3782, или в личные сообщения на CF.