Нижняя и верхняя границы
Реализуйте bisect_left и bisect_right с нуля, а затем применяйте их для поиска первой и последней позиций целевого значения
«Нижняя и верхняя границы» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Что такое нижняя и верхняя границы
Нижняя граница целевого значения в отсортированном массиве — это индекс первого элемента, большего или равного целевому значению (часто обозначается как bisect_left). Верхняя граница — это индекс первого элемента, строго большего целевого значения (bisect_right). Вместе они охватывают все вхождения целевого значения и позволяют выполнять запросы по диапазонам за O(log n).
Эти две операции лежат в основе многих задач на собеседованиях: подсчёта вхождений, поиска диапазона, определения позиции вставки и других.
arr = [1, 2, 2, 2, 3, 5]
# lower bound of 2 => index 1 (first element >= 2)
# upper bound of 2 => index 4 (first element > 2)
# occurrences of 2 => upper - lower = 4 - 1 = 3
print('lower bound of 2:', 1)
print('upper bound of 2:', 4)
print('count of 2:', 4 - 1)Реализация нижней границы (bisect_left)
bisect_left(arr, x) возвращает крайний левый индекс i, такой что arr[i] >= x, или len(arr), если все элементы меньше x. В реализации используется исключающая верхняя граница: hi = len(arr), условие цикла lo < hi и присваивание hi = mid, когда arr[mid] >= x. Это гарантирует, что результатом станет самая левая допустимая позиция.
def bisect_left(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < x:
lo = mid + 1
else:
hi = mid # arr[mid] >= x, so potential answer
return lo # lo == hi == insertion point
arr = [1, 2, 2, 2, 3, 5]
print(bisect_left(arr, 2)) # 1
print(bisect_left(arr, 0)) # 0 (before all)
print(bisect_left(arr, 6)) # 6 (after all)
print(bisect_left(arr, 3)) # 4Реализация верхней границы (bisect_right)
bisect_right(arr, x) возвращает крайний левый индекс i, такой что arr[i] > x. Отличается только одна строка от bisect_left: условие меняется с arr[mid] < x на arr[mid] <= x. Когда arr[mid] <= x, результат находится строго правее mid, поэтому устанавливаем lo = mid + 1; в противном случае сужаем диапазон справа.
def bisect_right(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= x:
lo = mid + 1 # arr[mid] <= x, so answer is strictly right
else:
hi = mid
return lo
arr = [1, 2, 2, 2, 3, 5]
print(bisect_right(arr, 2)) # 4
print(bisect_right(arr, 0)) # 0
print(bisect_right(arr, 5)) # 6
print(bisect_right(arr, 4)) # 5Подсчёт вхождений с обеими границами
Чтобы подсчитать вхождения целевого значения в отсортированном массиве за O(log n), примените обе границы: count = bisect_right(arr, target) - bisect_left(arr, target). Если count равен 0, целевое значение отсутствует. Это значительно быстрее линейного прохода и является стандартным подходом для запросов частот в отсортированных данных.
import bisect
def count_occurrences(arr, target):
left = bisect.bisect_left(arr, target)
right = bisect.bisect_right(arr, target)
return right - left
arr = [1, 2, 2, 2, 3, 3, 5]
print(count_occurrences(arr, 2)) # 3
print(count_occurrences(arr, 3)) # 2
print(count_occurrences(arr, 4)) # 0
print(count_occurrences(arr, 1)) # 1Поиск первой и последней позиции целевого значения
В задаче LeetCode 34 «Поиск первой и последней позиции элемента в отсортированном массиве» требуется вернуть [first_idx, last_idx] за O(log n). Первая позиция — это bisect_left(arr, target), но только если arr[result] == target. Последняя позиция — это bisect_right(arr, target) - 1. Если любая из проверок завершается неудачей, верните [-1, -1].
import bisect
def search_range(nums, target):
left = bisect.bisect_left(nums, target)
if left == len(nums) or nums[left] != target:
return [-1, -1]
right = bisect.bisect_right(nums, target) - 1
return [left, right]
print(search_range([5,7,7,8,8,10], 8)) # [3, 4]
print(search_range([5,7,7,8,8,10], 6)) # [-1, -1]
print(search_range([], 0)) # [-1, -1]Позиция вставки (LeetCode 35)
В задаче LeetCode 35 «Поиск позиции для вставки» спрашивается: куда следует вставить целевое значение, чтобы массив остался отсортированным? Это в точности bisect_left(arr, target). Если целевое значение существует, bisect_left возвращает его индекс. Если оно не существует, bisect_left возвращает индекс, куда его следовало бы вставить. Специальная обработка не требуется — одна и та же функция работает в обоих случаях.
import bisect
def searchInsert(nums, target):
return bisect.bisect_left(nums, target)
print(searchInsert([1,3,5,6], 5)) # 2 (exists at index 2)
print(searchInsert([1,3,5,6], 2)) # 1 (would insert between 1 and 3)
print(searchInsert([1,3,5,6], 7)) # 4 (would append at end)
print(searchInsert([1,3,5,6], 0)) # 0 (would prepend)Различие между bisect_left и bisect_right
Если дубликатов нет, bisect_left и bisect_right возвращают один и тот же индекс. Различие имеет значение только тогда, когда целевое значение встречается несколько раз. bisect_left указывает на первую копию, а bisect_right — на позицию сразу после последней копии. Всегда выбирайте функцию в зависимости от того, нужно ли вставить значение перед существующими копиями (слева) или после них (справа).
import bisect
arr = [1, 2, 2, 2, 3]
# Insert a new 2 before all existing 2s
print(bisect.bisect_left(arr, 2)) # 1
# Insert a new 2 after all existing 2s
print(bisect.bisect_right(arr, 2)) # 4
# For a value not in array, both give same insertion point
print(bisect.bisect_left(arr, 2.5)) # 4
print(bisect.bisect_right(arr, 2.5)) # 4Применение границ к запросам частот в отсортированном массиве
Если требуется эффективно обрабатывать множество запросов о частоте значений в диапазонах отсортированного массива, один раз заранее подготовьте отсортированный массив и используйте двоичный поиск для каждого запроса. Каждый запрос позволяет определить, «сколько элементов находится в диапазоне [lo, hi]?», за O(log n), а не за O(n). Этот шаблон встречается в задачах на подсчёт элементов в диапазоне значений после сортировки.
import bisect
def count_in_range(arr, lo, hi):
'''Count elements in arr with lo <= val <= hi. arr must be sorted.'''
left = bisect.bisect_left(arr, lo)
right = bisect.bisect_right(arr, hi)
return right - left
arr = sorted([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
print(arr) # [1,1,2,3,3,4,5,5,5,6,9]
print(count_in_range(arr, 3, 5)) # 6 (3,3,4,5,5,5)
print(count_in_range(arr, 1, 2)) # 3 (1,1,2)Двоичный поиск по пользовательскому ключу
Иногда ключом поиска служит не само сохранённое значение, а производное свойство. Модуль Python bisect напрямую не поддерживает функцию ключа, но двоичный поиск можно реализовать вручную, применяя ключ внутри цикла. Такой подход используется при поиске в списке объектов по одному из их атрибутов.
# Binary search on a list of (score, name) tuples by score
def lower_bound_by_score(records, min_score):
lo, hi = 0, len(records)
while lo < hi:
mid = lo + (hi - lo) // 2
if records[mid][0] < min_score:
lo = mid + 1
else:
hi = mid
return lo
records = [(50, 'Alice'), (72, 'Bob'), (72, 'Carol'), (88, 'Dave'), (95, 'Eve')]
idx = lower_bound_by_score(records, 72)
print(idx) # 1 (first record with score >= 72)
print(records[idx:]) # [(72,'Bob'),(72,'Carol'),(88,'Dave'),(95,'Eve')]Распространённые ошибки на собеседовании при работе с границами
Самая распространённая ошибка — забыть выполнить проверку после вызова bisect_left. Функция всегда возвращает допустимый индекс вставки, но не гарантирует, что элемент по этому индексу равен целевому значению. Всегда проверяйте arr[result] == target, прежде чем считать, что целевое значение найдено.
Вторая ошибка — использовать bisect_right, когда требуется первое вхождение: bisect_right возвращает позицию сразу после последнего вхождения, поэтому вычитание 1 даёт последнее, а не первое вхождение.
import bisect
arr = [1, 3, 5, 7]
target = 4
# bisect_left returns 2 (insertion point for 4 between 3 and 5)
idx = bisect.bisect_left(arr, target)
print(idx) # 2
# Validate: arr[2] is 5, not 4 => target absent
found = idx < len(arr) and arr[idx] == target
print('Found:', found) # FalseИтоги: когда использовать bisect_left, а когда bisect_right
Используйте bisect_left, когда требуется: найти первое вхождение целевого значения, получить точку вставки, которая сдвигает существующие копии вправо, или проверить существование целевого значения. Используйте bisect_right, когда требуется: получить позицию сразу после последнего вхождения, найти точку вставки после всех существующих копий или подсчитать элементы, меньшие или равные целевому значению (это значение равно bisect_right(arr, target)).
Обе функции работают за O(log n) и входят в стандартную библиотеку Python, поэтому их можно сразу импортировать и использовать, если только интервьюер не попросит реализовать их с нуля.
Быстрая проверка
Проверьте, насколько хорошо вы усвоили понятия из урока «Структуры данных и алгоритмы — подготовка к техническому собеседованию».
Итоги урока
В этом уроке вы узнали: bisect_left находит первый элемент, больший или равный целевому значению, bisect_right находит первый элемент, больший целевого значения (позицию сразу после последнего вхождения), а разность этих значений даёт число вхождений за O(log n). Далее мы рассмотрим двоичный поиск по пространству ответов, где область поиска представляет собой диапазон возможных ответов, а не индекс массива.
Часто задаваемые вопросы
Урок «Нижняя и верхняя границы» бесплатный?
Да — полный текст урока «Нижняя и верхняя границы» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Нижняя и верхняя границы»?
Реализуйте bisect_left и bisect_right с нуля, а затем применяйте их для поиска первой и последней позиций целевого значения Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Нижняя и верхняя границы»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Классический двоичный поиск: левый, правый, средний
- Двоичный поиск в повёрнутых и неотсортированных массивах
- Нижняя и верхняя границы
- Двоичный поиск по пространству ответов