Левая граница: первый элемент не меньше x

Коротко

Часто нужен не «есть ли x», а левая граница - индекс ПЕРВОГО элемента, который ≥ x (в C++ это lower_bound, в Python - bisect_left). Это позиция, куда x можно вставить, не нарушив порядок, и одновременно начало блока всех вхождений x, если они есть. Считается тем же двоичным поиском, но с ОДНИМ изменением: мы не выходим, найдя x, а продолжаем искать левее. Инвариант полуинтервала [lo, hi) меняет смысл: слева от lo все элементы < x, не левее hi - все ≥ x. Сдвиг: a[mid] < x → lo = mid+1, иначе hi = mid. В конце lo == hi - и это ответ.

Если ты пишешь поиск левой границы (первый элемент ≥ x) через инвариант «слева от lo всё < x, не левее hi всё ≥ x» и понимаешь, почему сравнение здесь строгое <, листай до «Теперь сам».

Как думаешь, чем «найти x» беднее, чем «найти границу»

Обычный двоичный поиск отвечает «да/нет» и, если элементов x несколько, вернёт КАКОЙ-ТО из них - непонятно, какой именно. А на практике вопросы почти всегда другие: «сколько раз x встречается?», «с какого индекса начинается блок троек?», «куда вставить новый элемент, чтобы массив остался сортированным?». На все три отвечает одно число - позиция ПЕРВОГО элемента, который не меньше x. Обычный поиск её не даёт: наткнувшись на x, он останавливается где попало внутри блока повторов. Значит, нужен поиск, который, найдя x, не радуется, а упрямо проверяет - а нет ли такого же ЛЕВЕЕ.

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

Полка книг, расставленных по году издания, и несколько книг одного года - 2020-го. Тебя просят: «дай самую левую книгу 2020 года». Ты не хватаешь первую попавшуюся 2020-ю - ты, найдя её, продолжаешь идти ВЛЕВО, пока слева не окажется год меньше. Останавливаешься там, где слева уже 2019-й, а под рукой - 2020-й. Это и есть левая граница: рубеж между «меньше x» и «x и больше». Даже если книг 2020-го на полке нет вовсе, ты покажешь щель, куда её надо было бы вставить, - между 2019-м и 2021-м.

Механизм: тот же поиск, но без раннего выхода

Инвариант полуинтервала [lo, hi) теперь несёт ДРУГОЙ смысл: всё, что левее lo, строго < x; всё, что не левее hi (индексы ≥ hi), - это ≥ x. Стартуем lo = 0, hi = len(a). Пока lo < hi:

mid = lo + (hi - lo) // 2
если a[mid] < x:  lo = mid + 1   # mid и левее - все < x, отбрасываем
иначе (a[mid] >= x): hi = mid     # mid, возможно, и есть граница - НЕ отбрасываем его

Ключевое отличие от прошлого урока - НЕТ ветки == x с ранним return. Когда a[mid] == x, мы попадаем в ветку >= x и двигаем hi = mid, то есть оставляем mid кандидатом и ищем, нет ли такого же левее. Цикл кончается при lo == hi; это число и есть левая граница - первый индекс, где a[i] >= x. Если все элементы < x, ответ len(a) (граница за концом); если все ≥ x, ответ 0.

Левая граница - рубеж между «меньше x» и «x или больше». Она же начало блока вхождений x и место вставки нового x.

Правило

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

Разбор: почему сравнение строгое (<), а не (≤)

Вся разница между «левой» и «правой» границей прячется в одном знаке. Здесь мы двигаем lo вправо только когда a[mid] СТРОГО меньше x (<). Значит на a[mid] == x мы НЕ двигаем lo, а идём в ветку hi = mid - тянем правый конец влево, продолжая искать такой же элемент левее. Так поиск «прилипает» к самому левому вхождению x. Поставь ≤ вместо < - и на a[mid] == x ты сдвинул бы lo вправо, перепрыгнув через вхождение x; поиск уехал бы правее блока и вернул уже ПРАВУЮ границу (первый элемент > x). Отсюда мнемоника: < тянет влево (lower), ≤ - вправо (upper). Один знак решает, к какому концу блока повторов ты прилипнешь.

Разбор: три вопроса, на которые отвечает одно число

Левая граница p - это сразу три ответа. Первый: СКОЛЬКО элементов строго меньше x? Ровно p (все они левее границы). Второй: КУДА вставить x, сохранив порядок? На позицию p - x встанет перед блоком равных или на своё место среди меньших и больших. Третий: ЕСТЬ ли x вообще? Проверь p < len(a) and a[p] == x: если да - x есть и блок начинается с p; если нет - x отсутствует, а p показывает щель, куда он бы встал. Одно значение закрывает поиск, вставку и подсчёт «меньших». А в паре с правой границей (следующий урок) оно ещё и мгновенно даёт число вхождений x.

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

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

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

Левая граница - рабочая лошадка любой работы с отсортированными данными. bisect_left в Python вставляет элементы, держа список сортированным (основа сортированных коллекций); lower_bound в C++ - тот же инструмент. На ней строят «найти ближайший не меньший» (потолок запроса), диапазонные запросы «сколько значений в [a, b]» (upper(b) − lower(a)), поиск по времени в логах (первое событие не раньше момента t). Везде, где данные упорядочены и вопрос звучит как «с какого места начинается…», ответ - левая граница. А поняв, что весь фокус - в знаке сравнения, ты за минуту переделаешь её в правую границу и покроешь вторую половину таких вопросов.

Теперь сам

В массиве [1, 4, 4, 4, 9] найди левую границу для x = 4. Пройди шаги (lo = 0, hi = 5) и скажи, чему равен ответ и что он означает.

Ответ. Шаг 1: mid = 0 + (5−0)//2 = 2, a[2] = 4, не меньше x (4 >= 4), значит hi = mid = 2. Участок [0, 2). Шаг 2: mid = 0 + (2−0)//2 = 1, a[1] = 4 >= 4, снова hi = mid = 1. Участок [0, 1). Шаг 3: mid = 0, a[0] = 1 < 4, значит lo = mid + 1 = 1. Теперь lo == hi == 1 - цикл кончился, ответ 1. Это индекс ПЕРВОЙ четвёрки: слева от него (индекс 0) стоит 1 < 4, а с индекса 1 начинается блок четвёрок. Заодно 1 - это число элементов строго меньше 4 (одна единица) и позиция, куда встала бы новая 4. Обрати внимание: на a[mid] == 4 поиск ни разу не остановился, а тянул hi влево - потому и прилип к самой левой четвёрке.

Главное

Левая граница (lower_bound, bisect_left) - индекс первого элемента ≥ x. Двоичный поиск с инвариантом [lo, hi): левее lo всё < x, не левее hi всё ≥ x; при a[mid] < x двигаем lo = mid + 1, иначе hi = mid. Раннего выхода на равенстве нет - ветка == x ведёт себя как «больше» и тянет границу влево; за это отвечает СТРОГИЙ знак < (а ≤ дал бы правую границу). Ответ lo == hi сразу решает три задачи: позиция вставки x, начало блока его вхождений и число элементов строго меньше x. Проверяй p < len(a) перед чтением a[p].