Первое и последнее вхождение: один шаблон бинарного поиска
В задаче LeetCode 34 нужно найти первое и последнее вхождение числа в отсортированном массиве за (O(\log n)). Хорошая проверка того, насколько уверенно ты владеешь бинарным поиском: найти само число мало, нужно ещё добраться до обоих краёв группы одинаковых элементов.
Если с обычным бинарным поиском ты уже знаком, попробуем посмотреть на него чуть иначе. Вместо двух разных циклов возьмём один шаблон и будем менять в нём только вопрос, на который отвечает функция check.
Универсальный шаблон в стиле Codeforces
Такой шаблон можно встретить в разборах на Codeforces. Возьмём его на вооружение у старших братьев в мире олимпиадного программирования.
На первый взгляд код немного непривычный: вместо l = m + 1 и r = m - 1 здесь просто l = m и r = m. Указатели не должны ни совпасть, ни пересечься: поиск закончится, когда они окажутся рядышком.
Идея такая: слева от искомой границы проверка отвечает «нет», справа «да». Нам нужно найти первую позицию с ответом «да»:
from collections.abc import Callable
def binary_search(nums: list[int], check: Callable[[int], bool]) -> int:
l, r = -1, len(nums)
while l + 1 < r:
m = (l + r) // 2
if check(m):
r = m
else:
l = m
return r
В nums передаём массив, а в check функцию, которая проверяет элемент на позиции m. Что именно она проверяет, зависит от задачи: чуть ниже начнём с обычного поиска числа.
Важно, чтобы при движении по индексам слева направо ответы шли сначала False, потом True и уже не менялись обратно. Допустимы и крайние случаи: все ответы True или все False; тогда функция вернёт соответственно 0 или len(nums).
Что означают указатели
Представим границу как водораздел между ответами «нет» и «да». Указатели держат его с двух сторон:
l: самая правая из уже известных позиций с результатомFalse.r: самая левая из уже известных позиций с результатомTrue.- Между ними: позиции, в которых ещё нужно разобраться.
Почему начинаем за границами массива
Обрати внимание на инициализацию: l = -1, r = len(nums). В привычном варианте поиска по элементам часто начинают с первого и последнего индекса, 0 и len(nums) - 1, а здесь оба указателя намеренно ставим за пределами массива:
Позиции: -1 | 0 1 2 3 4 | 5
Массив: | 1 3 5 7 9 |
l r
перед после
массивом массива
Так все настоящие элементы с самого начала оказываются между указателями. Нам не нужно заранее проверять первый или последний элемент, чтобы решить, на какой стороне водораздела он находится.
Позицию -1 условно считаем ложной, а len(nums) истинной. Это воображаемые опоры для поиска: мы не вызываем для них check и не читаем nums[-1] или nums[len(nums)].
Для поиска числа это удобно представлять так: перед массивом мысленно стоит минус бесконечность, а после массива плюс бесконечность. Для любого конечного target обе наши проверки, >= target и > target, на левом воображаемом элементе ложны, а на правом истинны:
Позиции: -1 | 0 1 2 3 4 | 5
Значения: −∞ | 1 3 5 7 9 | +∞
l r
Бесконечности здесь обозначают воображаемые значения, а не индексы: указатели по-прежнему равны -1 и len(nums). Мы ничего не добавляем в массив; этот образ лишь помогает понять, почему слева у нас гарантированное «нет», а справа гарантированное «да».
В Python запись nums[-1] действительно обращается к последнему элементу. Но присвоить переменной l число -1 и прочитать nums[-1] не одно и то же: в нашем коде к массиву обращается только проверка nums[m], а m всегда находится внутри массива.
m тоже никогда не становится -1 или len(nums). Благодаря условию l + 1 < r мы вычисляем середину только тогда, когда между указателями есть хотя бы один индекс, поэтому всегда выполняется l < m < r.
Например, при l = -1, r = 1 получаем m = 0. А при l = -1, r = 0 цикл уже не запустится: выражение (-1 + 0) // 2, которое в Python дало бы -1, мы вообще не вычисляем.
Правый указатель r никогда не станет -1. Он начинает с len(nums) и может измениться только на m, то есть на настоящий индекс от 0 до len(nums) - 1.
Поэтому результат поиска всегда находится от 0 до len(nums) включительно. Последнее значение означает «граница после всех элементов», а не индекс существующего элемента; для пустого массива сразу получаем 0.
Почему указатели двигаются без плюс одного и минус одного
Условие l + 1 < r означает «между указателями ещё есть хотя бы одна позиция». Когда остаются две соседние позиции, цикл заканчивается:
Между указателями ещё есть позиция:
Индекс: 2 3 4
l ? r
2 + 1 < 4 → True, продолжаем
Указатели стали соседними:
Индекс: 2 3
l r
2 + 1 < 3 → False, останавливаемся
Пока цикл работает, середина m находится строго между l и r. Поэтому присваивание l = m или r = m обязательно приближает указатели друг к другу, даже без + 1 и - 1.
Если check(m) истинна, справа от m тоже всё истинно, и можно поставить r = m. Если ложна, слева от m тоже всё ложно, и можно поставить l = m.
В конце указатели становятся соседними. Между последним False и первым True больше ничего нет, поэтому ответом будет r.
Если бы мы оставили обновления l = m и r = m, но написали while l < r, на соседних указателях поиск мог бы зациклиться. Например, при l = 2, r = 3 получаем m = 2: присваивание l = m уже ничего не меняет, а условие l < r всё ещё истинно.
То есть обновления указателей и условие остановки работают вместе. Здесь не нужно добиваться l == r: специально останавливаемся на l + 1 == r.
Сначала обычный поиск числа
Прежде чем искать два края группы одинаковых элементов, найдём одно число в простом массиве. Пусть нам нужно найти 7:
Индексы: 0 1 2 3 4
nums: 1 3 5 7 9
Первое желание: написать в check(m) проверку nums[m] == target. Но тогда получим False, False, False, True, False: после семёрки ответ снова становится ложным, а для нашего шаблона это не подходит.
Спросим иначе: «элемент уже не меньше искомого?». Для target = 7 проверка будет такой:
def check(m: int) -> bool:
return nums[m] >= target
Теперь массив разделяется на две понятные части. Слева все элементы меньше 7, справа все элементы не меньше 7:
Индексы: 0 1 2 | 3 4
nums: 1 3 5 | 7 9
check: False False False | True True
l | r
< 7 | >= 7
На схеме указатели уже стоят у водораздела. Посмотрим, как они туда добрались, начиная с l = -1 и r = 5:
| Шаг | l | r | m | nums[m] | check(m) | Действие |
|---|---|---|---|---|---|---|
| 1 | -1 | 5 | 2 | 5 | False | l = 2 |
| 2 | 2 | 5 | 3 | 7 | True | r = 3 |
После второго шага l = 2, r = 3: указатели стоят рядом. Условие l + 1 < r ложно, поэтому возвращаем r = 3, индекс семёрки.
Но сам шаблон ищет первый элемент >= target, а не обязательно равный target. Например, при поиске 6 он тоже вернул бы позицию семёрки, поэтому для обычного поиска нужна финальная проверка:
def find_target(nums: list[int], target: int) -> int:
def check(m: int) -> bool:
return nums[m] >= target
r = binary_search(nums, check)
if r < len(nums) and nums[r] == target:
return r
return -1
Если target больше всех элементов, функция binary_search вернёт len(nums). Проверка r < len(nums) не даст обратиться к несуществующему элементу.
Что здесь универсального
В примере проверка nums[m] >= target дала последовательность False, False, False, True, True. В другой задаче смысл вопроса может быть другим, но нужна та же форма:
False False False | True True True
|
водораздел
Сам бинарный поиск не сравнивает числа 1, 3, 5, 7, 9 с target: за это отвечает check. Он просто ищет первый True, а если настоящих True нет, возвращает len(nums).
Именно поэтому шаблон универсален: ему важно не содержание вопроса, а порядок ответов False, затем True. Это называют монотонным условием.
Тот же цикл можно использовать и в целочисленном поиске по ответу, а не только по индексам массива. Тогда вместо -1 и len(nums) выбираем границы своего диапазона: слева условие должно быть заведомо ложным, справа истинным.
Возвращаемся к первому и последнему вхождению
Дан массив целых чисел nums, отсортированный по неубыванию, и число target; нужно вернуть индексы его первого и последнего вхождения, а при отсутствии числа вернуть [-1, -1] (условие LeetCode). Массив может быть пустым и содержать дубликаты, его длина не превышает (10^5), значения элементов и target находятся от (-10^9) до (10^9) (ограничения LeetCode).
Возьмём такой пример и будем использовать его дальше. Индексы считаем с нуля:
nums = [1, 2, 2, 2, 5]
target = 2
ответ = [1, 3]
Здесь одного вхождения уже недостаточно, нужны первое и последнее. Найдём их тем же шаблоном: один водораздел пройдёт перед всеми двойками, другой после них.
Левая граница: первый элемент не меньше target
Для первого вхождения подойдёт уже знакомый вопрос: «элемент не меньше target?». Проверку из обычного поиска можно оставить без изменений:
def check_left(m: int) -> bool:
return nums[m] >= target
В отсортированном массиве эта проверка монотонна: как только встретился элемент >= target, все элементы правее тоже >= target. В нашем примере получаем:
Индексы: 0 | 1 2 3 4
nums: 1 | 2 2 2 5
check: False | True True True True
l | r
< 2 | >= 2
После цикла l = 0, r = 1. Возвращаем 1: индекс первой двойки, он же позиция вставки перед всеми двойками.
Здесь нет противоречия между словами «левая граница» и возвращением правого указателя. r стоит справа от водораздела, но именно там начинается группа равных элементов.
Правая граница: первый элемент строго больше target
Для правой границы меняем только проверку. Теперь все равные элементы должны остаться слева:
def check_right(m: int) -> bool:
return nums[m] > target
Эта проверка тоже монотонна. Но водораздел теперь находится после всех двоек:
Индексы: 0 1 2 3 | 4
nums: 1 2 2 2 | 5
check: False False False False | True
l | r
<= 2 | > 2
После цикла l = 3, r = 4. Функция возвращает 4: позицию сразу после всех двоек, а не индекс последней двойки.
Поэтому последнее вхождение находится на позиции r - 1. Сам цикл по-прежнему возвращает r, и его код вообще не меняется.
Если массив заканчивается на target
Допустим, массив выглядит так: nums = [1, 2, 2, 2]. Для проверки nums[m] > 2 ни одного настоящего True нет:
Индексы: 0 1 2 3 | 4
nums: 1 2 2 2 | конец
check: False False False False |
l | r
Получаем r = 4 = len(nums): ни один элемент не оказался строго больше двойки, поэтому правый указатель так и остался на своей начальной позиции. Это и есть место для вставки новой двойки после всех существующих:
До вставки: [1, 2, 2, 2]
После вставки: [1, 2, 2, 2, 2]
^
индекс 4
Здесь мы только нашли позицию, сам код ничего не вставляет. Последнее существующее вхождение находится на позиции r - 1 = 3.
Важно: именно поиск правой границы с проверкой > target возвращает len(nums), если массив заканчивается на target. Поиск левой границы с проверкой >= target в этом же примере вернёт 1, индекс первой двойки.
В этом ещё одно отличие от поиска, который возвращает индекс найденного элемента или -1: наш шаблон возвращает позицию границы, в том числе после массива. Поэтому r == len(nums) является нормальным результатом, но читать nums[r] в таком случае нельзя.
Собираем ответ из двух границ
Назовём результат первого поиска left, а второго right. В нашем примере они расположатся так:
Индексы: 0 | 1 2 3 | 4
nums: 1 | 2 2 2 | 5
left right
left = 1: позиция первой двойки.right = 4: позиция сразу после последней двойки.right - 1 = 3: позиция самой последней двойки.
Получаем ответ [left, right - 1], то есть [1, 3]. Первый поиск уже дал нужный индекс, а от результата второго отступаем на одну позицию.
Осталось разобраться с отсутствующим числом. Если target в массиве нет, проверки >= target и > target дают одинаковые результаты: ведь равных элементов, на которых они могли бы различаться, нет.
Например, для того же массива и target = 3 получаем одну и ту же картину. Оба поиска останавливаются на индексе 4:
nums: 1 2 2 2 | 5
>= 3: False False False False | True
> 3: False False False False | True
left = right = 4
Поэтому left == right означает, что искомого числа нет. Если же число есть, left указывает на первое вхождение, а right стоит после последнего, поэтому left < right.
В обычном поиске мы проверяли равенство найденного элемента target. Здесь отдельная проверка nums[left] == target уже не нужна: наличие числа определяется сравнением результатов двух поисков.
Алгоритм по шагам
- Передаём в бинарный поиск массив
numsи проверкуnums[m] >= target. - Сохраняем полученную левую границу в
left. - Вызываем тот же бинарный поиск с проверкой
nums[m] > target. - Сохраняем результат в
right: это позиция первого элемента> targetилиlen(nums), если такого элемента нет. - Если
left == right, возвращаем[-1, -1]. - Иначе возвращаем
[left, right - 1].
Как двигаются указатели
Проследим оба поиска для nums = [1, 2, 2, 2, 5], target = 2. В таблицах l и r указаны до соответствующего шага.
Левая граница: nums[m] >= 2
| Шаг | l | r | m | nums[m] | check(m) | Действие |
|---|---|---|---|---|---|---|
| 1 | -1 | 5 | 2 | 2 | True | r = 2 |
| 2 | -1 | 2 | 0 | 1 | False | l = 0 |
| 3 | 0 | 2 | 1 | 2 | True | r = 1 |
Остановились на l = 0, r = 1. Получили left = 1.
Правая граница: nums[m] > 2
| Шаг | l | r | m | nums[m] | check(m) | Действие |
|---|---|---|---|---|---|---|
| 1 | -1 | 5 | 2 | 2 | False | l = 2 |
| 2 | 2 | 5 | 3 | 2 | False | l = 3 |
| 3 | 3 | 5 | 4 | 5 | True | r = 4 |
Остановились на l = 3, r = 4. Получили right = 4, поэтому ответ задачи [1, 3].
Код на Python
Остаётся соединить шаблон и две проверки. В binary_search передаём массив и нужную функцию check: сам цикл не должен знать, какую границу мы сейчас ищем.
from collections.abc import Callable
def binary_search(nums: list[int], check: Callable[[int], bool]) -> int:
l, r = -1, len(nums)
while l + 1 < r:
m = (l + r) // 2
if check(m):
r = m
else:
l = m
return r
class Solution:
def searchRange(self, nums: list[int], target: int) -> list[int]:
def check_left(m: int) -> bool:
return nums[m] >= target
def check_right(m: int) -> bool:
return nums[m] > target
left = binary_search(nums, check_left)
right = binary_search(nums, check_right)
# Границы совпали: target отсутствует.
if left == right:
return [-1, -1]
# right стоит сразу после последнего вхождения.
return [left, right - 1]
В вызове binary_search(nums, check_left) передаётся сама функция проверки, без скобок. Уже внутри поиска она будет вызываться с очередным индексом m.
Обе проверки видят nums и target из функции searchRange, внутри которой они объявлены. Сам binary_search получает этот же массив и использует его длину, а все сравнения оставляет проверке.
Именованные проверки здесь выбраны для наглядности. Если привычнее lambda, те же вызовы можно записать короче, не меняя binary_search:
left = binary_search(nums, lambda m: nums[m] >= target)
right = binary_search(nums, lambda m: nums[m] > target)
Краевые случаи
Все эти случаи обрабатываются тем же кодом. Дополнительные ветвления для пустого массива, одного элемента или одинаковых значений не нужны.
- Пустой массив: оба поиска сразу возвращают
0, не вызываяcheck; границы равны, ответ[-1, -1]. - Один элемент, равный target: границы
0и1, ответ[0, 0]. - Все элементы равны target: границы
0иlen(nums), ответ[0, len(nums) - 1]. - Target меньше всех элементов: обе границы равны
0, ответ[-1, -1]. - Target больше всех элементов: обе границы равны
len(nums), ответ[-1, -1]. - Target отсутствует между элементами: обе границы совпадают в позиции его вставки, ответ
[-1, -1]. - Отрицательные значения: ничего не меняется, проверки используют обычное сравнение чисел.
Сложность
Пусть (n) обозначает длину массива. На каждом шаге расстояние между l и r уменьшается примерно вдвое, а наши проверки >= target и > target занимают (O(1)).
Два поиска выполняются последовательно, поэтому их время складывается: итог (O(\log n)), а не (O(\log^2 n)). Для пустого массива оба цикла сразу пропускаются и всё решение занимает (O(1)).
Дополнительная память составляет (O(1)): несколько индексов, две функции проверки и ответ из двух чисел. Булевы массивы на схемах существуют только для объяснения, код их не создаёт.
Связь с bisect_left и bisect_right
В стандартной библиотеке Python bisect_left возвращает позицию вставки перед всеми равными элементами, а bisect_right после них (документация Python). Поэтому наши два вызова соответствуют этим двум операциям:
from bisect import bisect_left, bisect_right
left = bisect_left(nums, target)
right = bisect_right(nums, target)
Сборка ответа остаётся прежней: при совпадении границ возвращаем [-1, -1], иначе [left, right - 1]. Но в этом разборе мы написали поиск сами, чтобы понять устройство обеих границ.
Вывод
Не нужно запоминать два отдельных алгоритма для первого и последнего вхождения. Достаточно одного шаблона, который ищет первый True, и двух вопросов: «элемент уже не меньше target?» и «элемент уже строго больше target?».
В обоих случаях цикл одинаковый и возвращает r. Никаких l = m + 1 или r = m - 1: указатели просто приближаются друг к другу, пока не станут соседними.
Если target есть в массиве, первый поиск сразу даёт индекс первого вхождения, а результат второго нужно уменьшить на единицу. Если результаты двух поисков совпали, числа в массиве нет.
🐆