Казалось бы, по бинпоиску написано столько материалов, что все должны знать, как писать его, однако в каждом материале похоже рассказывается свой подход, и я вижу, что люди теряются и допускают ошибки в такой простой штуке. Поэтому я хочу рассказать о подходе, который нахожу наиболее элегантным. Из всего многообразия статей, я увидел свой подход только в этом комментарии (но менее обобщённый).
Проблема
Предположим, вы хотите найти последний элемент в отсортированном массиве, меньший 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;
Заключение
Надеюсь, я разъяснил кое-что, и часть из вас переключится на эту имплементацию. Для уточнения, иногда другие имплементации могут оказаться более подходящими, например, в интерактивных задачах – когда нам нужно мыслить в терминах интервала поиска, а не в терминах первого/последнего числа, для которого что-то выполняется.
Я напоминаю, что даю частные уроки по спортивному программированию, цена – $25/ч. Пишите мне в Telegram, Discord: rembocoder#3782, или в личные сообщения на CF.
