Разбор задачи · LeetCode 34

34. Find First and Last Position of Element in Sorted Array

08.11.2026 · Глеб Михайлов
Условие на LeetCode ↗

Первое и последнее вхождение: один шаблон бинарного поиска

В задаче 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 = -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, 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 уже не нужна: наличие числа определяется сравнением результатов двух поисков.

Алгоритм по шагам

  1. Передаём в бинарный поиск массив nums и проверку nums[m] >= target.
  2. Сохраняем полученную левую границу в left.
  3. Вызываем тот же бинарный поиск с проверкой nums[m] > target.
  4. Сохраняем результат в right: это позиция первого элемента > target или len(nums), если такого элемента нет.
  5. Если left == right, возвращаем [-1, -1].
  6. Иначе возвращаем [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)

Краевые случаи

Все эти случаи обрабатываются тем же кодом. Дополнительные ветвления для пустого массива, одного элемента или одинаковых значений не нужны.

Сложность

Пусть (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 есть в массиве, первый поиск сразу даёт индекс первого вхождения, а результат второго нужно уменьшить на единицу. Если результаты двух поисков совпали, числа в массиве нет.

🐆