Правая граница и число вхождений

Если ты понимаешь, что правая граница - это bisect_right (первый элемент > x), что число вхождений x равно правая − левая, и почему знак здесь ≤, а не <, листай до «Теперь сам».

Как думаешь, как за log n сосчитать, сколько раз встречается x

Наивно «сколько раз встречается x» считают линейным проходом - Θ(n). Но массив ОТСОРТИРОВАН, а значит все вхождения x лежат одним непрерывным блоком: сначала меньшие, потом блок равных, потом большие. Чтобы измерить блок, хватит двух его КРАЁВ. Левый край мы уже умеем находить - это левая граница из прошлого урока. Остался правый: индекс, где блок равных заканчивается и начинаются большие. Найдём оба за Θ(log n) - и число вхождений получим вычитанием, не считая элементы по одному. Вопрос лишь в том, как чуть изменить поиск, чтобы он прилипал не к левому краю блока, а к правому.

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

Та же полка книг по годам, снова несколько книг 2020-го. В прошлый раз ты искал самую ЛЕВУЮ. Теперь тебя просят показать, где блок 2020-го КОНЧАЕТСЯ, - палец должен встать на первую книгу 2021 года (или дальше, если 2021-го нет). Ты снова идёшь двоичным поиском, но, встретив 2020-й, продолжаешь идти ВПРАВО, а не влево: 2020-е тебя больше не останавливают, ты ищешь первый год строго больше. Палец замирает сразу за последней книгой 2020-го. Расстояние между двумя пальцами - левым (начало блока) и правым (сразу за концом) - и есть число книг 2020 года.

Механизм: сдвинуть только знак сравнения

Инвариант полуинтервала [lo, hi) для правой границы: левее lo все элементы ≤ x, не левее hi - все > x. Стартуем lo = 0, hi = len(a). Пока lo < hi:

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

Сравни с левой границей: там lo двигался при a[mid] < x, здесь - при a[mid] <= x. Всё различие - в одном знаке. Из-за ≤ теперь ветку a[mid] == x мы относим к «нужно идти ВПРАВО», то есть проскакиваем вхождения x и прилипаем к первому строго большему. Ответ lo == hi - индекс первого элемента > x, он же конец блока x. Число вхождений:

левая  = lower_bound(a, x)   # первый ≥ x
правая = upper_bound(a, x)   # первый > x
количество = правая - левая

Правило

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

Разбор: как один знак переключает левую и правую границу

Соберём обе границы рядом и увидим, что это ОДИН алгоритм с переключателем. Левая: lo = mid + 1 при a[mid] < x. Правая: lo = mid + 1 при a[mid] <= x. Разница - только в том, куда отнести случай a[mid] == x. Левая относит его к «оставить, искать левее» (ветка hi = mid) - и прилипает к НАЧАЛУ блока. Правая относит к «отбросить, идти правее» (ветка lo = mid + 1) - и уезжает за КОНЕЦ блока. Поэтому запомни не два кода, а один и мнемонику: строгий < тянет к левому краю (lower), нестрогий ≤ - за правый (upper). Всё остальное - стартовые границы, mid, условие цикла - идентично. Это типичная сила инварианта: меняешь смысл на волосок - получаешь новый инструмент, не переписывая каркас.

Разбор: почему [левая, правая) - это ровно все вхождения x

Докажем, что полуинтервал [левая, правая) накрывает вхождения x без промахов и без лишнего. Левая граница по определению - первый индекс, где a[i] >= x; так как массив отсортирован, всё до неё строго < x (вхождений x там нет). Правая граница - первый индекс, где a[i] > x; всё до неё ≤ x, а всё от неё и правее строго > x (вхождений x там тоже нет). Значит вхождения x могут быть только между ними, в [левая, правая). И они там ДЕЙСТВИТЕЛЬНО все == x: элементы этого участка одновременно ≥ x (правее левой границы) и ≤ x (левее правой), а ≥ x и ≤ x вместе дают == x. Значит длина участка - это ровно число вхождений x. Если x в массиве нет, обе границы совпадут (левая == правая), участок пуст, число вхождений 0 - и всё сходится.

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

Первая ошибка - взять для правой границы строгий знак < (как у левой): тогда обе границы совпадут с левой, «число вхождений» выйдет 0 даже там, где x есть. Знак ≤ - суть правой границы, не описка. Вторая - считать вхождения линейным проходом от левой границы вправо: это Θ(число вхождений), а если весь массив состоит из x, деградирует до Θ(n) - двоичная правая граница даёт Θ(log n) при любом размере блока. Третья - перепутать, что upper_bound указывает СРАЗУ ЗА последним x, а не на него: последний x стоит на индексе правая − 1, читать a[правая] для получения x неверно (там уже больший элемент или конец массива).

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

Пара «левая-правая граница» - стандартный способ работать с блоками равных в отсортированных данных. Диапазонный запрос «сколько значений попадает в [a, b]» считается как upper_bound(b) − lower_bound(a) за Θ(log n) - основа аналитики по отсортированным логам, гистограмм, перцентилей. bisect_right в Python вставляет элемент ПОСЛЕ равных ему (устойчивая вставка по времени прихода), bisect_left - перед; выбор между ними - это выбор между правой и левой границей. В базах данных диапазонное сканирование по индексу - ровно это: найти левую границу диапазона и идти до правой. Понимая, что весь набор инструментов - это один поиск с переключателем знака, ты перестаёшь заучивать bisect_left/bisect_right/lower_bound/upper_bound как четыре разные вещи.

Теперь сам

В массиве [3, 3, 3, 3] (все элементы - тройки) найди левую и правую границу для x = 3 и число вхождений. Что покажет каждая граница?