Бинарный поиск в C++: почему мой ручной бинпоиск иногда зацикливается, а STL — нет?
Пишу ручной целочисленный бинпоиск, и на некоторых входах он зависает в бесконечном цикле, хотя данные корректны. С lower_bound всё ок. Что не так с моим while (lo <= hi) и обновлением границ?
2 ответа
Зацикливание почти всегда — несогласованность между способом вычисления mid и сдвигом границ. Бесконечный цикл возникает, когда mid может остаться равным lo (или hi), а граница при этом не сдвигается строго.
Два безопасных канонических варианта:
A. Поиск точного значения, замкнутый интервал [lo, hi]:
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == key) return mid;
if (a[mid] < key) lo = mid + 1; // строго +1
else hi = mid - 1; // строго -1
}
return -1;
Здесь обе границы двигаются строго (mid ± 1), цикл всегда сужается — зависнуть нельзя.
B. Поиск границы, полуинтервал [lo, hi) (как в lower_bound):
int lo = 0, hi = n;
while (lo < hi) {
int mid = lo + (hi - lo) / 2; // округление вниз
if (a[mid] < key) lo = mid + 1;
else hi = mid; // hi = mid (НЕ mid-1)
}
// lo — первая позиция с a[lo] >= key
Здесь hi = mid без −1, но lo = mid + 1 строго. Поскольку mid округляется вниз и mid < hi всегда при lo < hi, ветка hi = mid строго уменьшает hi. Зависания нет.
Классическая ошибка-зацикливание: смешать стили — взять while (lo < hi), mid = (lo+hi)/2 (вниз) и lo = mid (без +1). При lo + 1 == hi будет mid = lo, и lo = mid ничего не меняет → вечный цикл. Правило: если в какой-то ветке ставишь границу = mid (не ±1), то mid должен округляться в сторону противоположной границы, а вторая ветка обязана двигать границу строго.
Чтобы не держать это в голове на контесте — используй STL: lower_bound/upper_bound/binary_search для значений, partition_point для произвольного монотонного предиката. partition_point(begin, end, pred) возвращает первую позицию, где pred становится ложным — это ровно «бинпоиск по предикату» без шанса зациклиться. Ручной бинпоиск пиши только когда предикат завязан на тяжёлую проверку (бинпоиск по ответу), и тогда строго придерживайся одного из двух шаблонов выше. И помни про переполнение mid: всегда lo + (hi - lo) / 2, не (lo + hi) / 2.