Казалось бы, по бинпоиску написано столько материалов, что все должны знать, как писать его, однако в каждом материале похоже рассказывается свой подход, и я вижу, что люди теряются и допускают ошибки в такой простой штуке. Поэтому я хочу рассказать о подходе, который нахожу наиболее элегантным. Из всего многообразия статей, я увидел свой подход только в этом [комментарии](https://codeforces.me/blog/entry/9901?#comment-153756) (но менее обобщённый).↵
↵
UPD: Также у [user:nor,2022-05-29] в [блоге](https://codeforces.me/blog/entry/96699).↵
↵
### Проблема↵
↵
Предположим, вы хотите найти последний элемент в отсортированном массиве, меньший `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`, слишком большое может привести к переполнению.↵
↵
### Пример↵
↵
[problem: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;↵
~~~~↵
↵
### Заключение↵
↵
Надеюсь, я разъяснил кое-что, и часть из вас переключится на эту имплементацию. Для уточнения, иногда другие имплементации могут оказаться более подходящими, например, в интерактивных задачах – когда нам нужно мыслить в терминах интервала поиска, а не в терминах первого/последнего числа, для которого что-то выполняется.↵
↵
**Я напоминаю, что даю частные уроки по спортивному программированию, цена – $350/ч. Пишите мне в [Telegram](https://t.me/rembocoder), Discord: rembocoder#3782, или в личные сообщения на CF.**
↵
UPD: Также у [user:nor,2022-05-29] в [блоге](https://codeforces.me/blog/entry/96699).↵
↵
### Проблема↵
↵
Предположим, вы хотите найти последний элемент в отсортированном массиве, меньший `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`, слишком большое может привести к переполнению.↵
↵
### Пример↵
↵
[problem: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;↵
~~~~↵
↵
### Заключение↵
↵
Надеюсь, я разъяснил кое-что, и часть из вас переключится на эту имплементацию. Для уточнения, иногда другие имплементации могут оказаться более подходящими, например, в интерактивных задачах – когда нам нужно мыслить в терминах интервала поиска, а не в терминах первого/последнего числа, для которого что-то выполняется.↵
↵
**Я напоминаю, что даю частные уроки по спортивному программированию, цена – $
