Двоичный поиск: инвариант полуинтервала

Если ты пишешь двоичный поиск через полуинтервал [lo, hi), знаешь, почему граница сдвигается на mid+1 или на mid, и можешь доказать завершаемость через убывание hi−lo, листай до «Теперь сам».

Как думаешь, почему двоичный поиск так легко испортить

Идея двоичного поиска проста: массив отсортирован, берём середину, и если искомое меньше - весь правый кусок можно выбросить, если больше - левый. За log n шагов от миллиона остаётся один. Но именно эту простую вещь программисты ломают чаще всего: поиск то зацикливается, то промахивается на один элемент, то падает на пустом входе. Причина всегда одна - НЕЧЁТКАЯ ГРАНИЦА: непонятно, какие индексы ещё «в игре», а какие уже отброшены, и mid то включают в отброшенный кусок, то нет. Лечится это не внимательностью, а одним решением, принятым раз и навсегда: чётко задать, что означают lo и hi, и на каждом шаге беречь это значение.

На что это похоже

Игра «угадай число от 1 до 100»: ведущий говорит «больше» или «меньше». Ты держишь в голове ОТРЕЗОК, где число ещё может быть, - скажем, «от 30 до 60». Назвал 45, услышал «больше» - и мгновенно сдвигаешь ЛЕВУЮ границу: теперь «от 46 до 60», и число 45 из игры выбыло навсегда. Ты никогда не назовёшь его снова, потому что честно вычеркнул. Двоичный поиск - та же дисциплина: «отрезок, где ответ ещё может быть» - это и есть инвариант, а сдвиг границы после сравнения - честное вычёркивание проверенного.

Механизм: полуинтервал [lo, hi) и три исхода сравнения

Договоримся: активный участок - это ПОЛУИНТЕРВАЛ [lo, hi), то есть индексы lo, lo+1, …, hi−1 (левый конец включён, правый - НЕТ). Инвариант: ответа нет ни левее lo, ни правее-или-в hi. Стартуем с lo = 0, hi = len(a) - весь массив. Пока lo < hi (участок непуст):

mid = (lo + hi) // 2          # середина, всегда lo ≤ mid < hi
если a[mid] == x:  нашли, возвращаем mid
если a[mid] <  x:  lo = mid + 1   # x правее mid; mid и всё левее - вон
иначе (a[mid] > x): hi = mid       # x левее mid; сам mid тоже вон (правый конец не входит)

Заметь асимметрию: при a[mid] < x пишем mid + 1 (mid проверен, он не ответ), а при a[mid] > x пишем mid без плюс-единицы - потому что правый конец hi в участок НЕ входит, значит hi = mid уже исключает сам mid. Полуинтервал делает этот сдвиг единообразным. Если цикл дошёл до lo == hi - участок пуст, элемента нет.

Правило

Двоичный поиск ищет в отсортированном массиве за Θ(log n), храня инвариант полуинтервала [lo, hi): ответа нет левее lo и не левее hi. Пока lo < hi, берём mid = (lo + hi) // 2; при a[mid] < x двигаем lo = mid + 1, при a[mid] > x - hi = mid. Каждый шаг строго уменьшает hi − lo, поэтому цикл всегда завершается, а за log₂ n шагов участок сойдётся к пустому или к ответу. Единая договорённость о границах - вот что делает поиск неломающимся.

Разбор: почему цикл обязан закончиться и не зациклиться

Завершаемость - отдельный вопрос, и он держится на том, что hi − lo СТРОГО убывает. Проверим оба сдвига. При a[mid] < x: lo становится mid + 1, а mid ≥ lo, значит новый lo хотя бы lo + 1 - участок укоротился минимум на 1. При a[mid] > x: hi становится mid, а mid = (lo + hi)//2 < hi (целочисленное деление при lo < hi даёт mid < hi), значит hi строго уменьшился. В обоих случаях hi − lo падает хотя бы на 1 и снизу ограничен нулём - цикл не может крутиться вечно. А вот классическая ошибка: написать lo = mid вместо lo = mid + 1. Тогда при участке из двух элементов mid совпадёт с lo, lo не сдвинется, и цикл ЗАВИСНЕТ. Плюс-единица - не украшение, а условие завершаемости.

Разбор: почему (lo + hi) // 2, а не (lo + hi) / 2 и не что-то хитрее

Середину берут целочисленным делением (lo + hi) // 2 - округление вниз. Это гарантирует lo ≤ mid < hi при lo < hi: mid всегда попадает В участок и никогда не совпадает с правым концом hi (который в участок и не входит). Именно поэтому сдвиг hi = mid корректен - он исключает непроверенный правый конец и проверенный mid заодно. В языках с ограниченным целым (C, Java) вместо (lo + hi)//2 пишут lo + (hi − lo)//2 - иначе сумма lo + hi на огромных массивах может ПЕРЕПОЛНИТЬ тип, и mid станет отрицательным (знаменитая ошибка, прожившая в стандартной библиотеке Java девять лет). В Python целые безразмерны, переполнения нет, но привычку писать lo + (hi − lo)//2 стоит завести - она переносится на любой язык.

Что ломается без этого

Первая беда - смешать типы границ: то hi включён, то нет. Определись раз: у нас hi НЕ входит в участок ([lo, hi)), и тогда hi = mid и старт hi = len(a) согласованы. Смешаешь с вариантом «hi включён» - получишь либо промах на один, либо выход за массив. Вторая - lo = mid вместо mid + 1: зависание, разобрали выше. Третья - забыть, что массив ДОЛЖЕН быть отсортирован: на неупорядоченных данных двоичный поиск даёт бессмысленный ответ, потому что «выбросить половину» опирается на порядок. Четвёртая - неверное условие цикла (lo <= hi при полуинтервале): лишний шаг на пустом участке и чтение a[hi] за границей.

Зачем это в работе

Двоичный поиск - самый частый способ превратить Θ(n) в Θ(log n), и он повсюду: поиск в отсортированном массиве, bisect в Python, lower_bound в C++, поиск по странице в базе данных, вход в B-дерево на каждом узле. Но ценность урока шире самого поиска: инвариант полуинтервала - это образец того, как вообще писать циклы с границами, чтобы они не ломались. Ту же дисциплину «что означают мои границы и как я берегу это на каждом шаге» ты применишь к слиянию, к разбиению быстрой сортировки, к скользящему окну. А ещё двоичный поиск - каркас для следующих уроков: чуть изменив условие сдвига, мы научимся искать не сам элемент, а ЛЕВУЮ и ПРАВУЮ его границу среди повторов.

Теперь сам

Ты ищешь x = 6 в массиве [1, 3, 5, 7] (индексы 0..3). Стартуем lo = 0, hi = 4. Пройди шаги по правилу и скажи, чему в конце равны lo и hi и что это означает.