bisect_left и bisect_right
Находите позиции вставки в отсортированном списке
«bisect_left и bisect_right» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Ищите без шаблонного кода
Модуль Python bisect предоставляет проверенный двоичный поиск для отсортированных списков. Цикл, написанный вручную, не нужен — значит, не придётся отлаживать ошибки смещения на единицу.
import bisectПозиции вставки, а не логические значения
Вместо true или false функция bisect возвращает индекс, куда можно вставить значение, сохранив сортировку списка. В этом индексе и заключается настоящая сила функции.
a = [1, 3, 3, 3, 7]bisect_left смещается влево
bisect_left возвращает первую позицию, куда можно поместить значение. При наличии дубликатов она оказывается перед всеми равными элементами, а не после них.
bisect.bisect_left(a, 3) # 1bisect_right смещается вправо
bisect_right возвращает позицию сразу после последнего равного элемента. При наличии дубликатов она оказывается после каждого совпадающего значения.
bisect.bisect_right(a, 3) # 4Подсчитайте равные элементы
Вычтите левую границу из правой, чтобы посчитать дубликаты значения за O(log n). Разность right и left даёт точное количество его появлений.
lo = bisect.bisect_left(a, 3)
hi = bisect.bisect_right(a, 3)
print(hi - lo) # 3Существовало ли это значение?
Чтобы проверить принадлежность, получите i с помощью bisect_left и убедитесь, что a[i] равно цели. Сначала проверьте, не достигло ли i длины списка.
i = bisect.bisect_left(a, x)
found = i < len(a) and a[i] == xПервый элемент не меньше X
bisect_left также находит первый элемент, больший или равный x. Этот индекс сразу указывает на ответ для нижней границы.
i = bisect.bisect_left(a, x) # first >= xПервый элемент, который строго больше
Нужен первый элемент, строго больший x? bisect_right напрямую возвращает этот индекс — аналог верхней границы.
i = bisect.bisect_right(a, x) # first > xВставляйте, сохраняя сортировку
insort за один вызов находит место и вставляет элемент, сохраняя порядок списка. Это удобно, когда вы строите отсортированную структуру на лету.
bisect.insort(a, 5) # a stays sortedИщите внутри окна
Необязательные аргументы lo и hi ограничивают поиск срезом. Это позволяет не создавать копию, если вас интересует только поддиапазон.
bisect.bisect_left(a, x, 2, 5)Ключи через вспомогательный список
bisect сравнивает элементы целиком, поэтому для поиска по полю создайте параллельный список только с нужными ключами и применяйте bisect к нему.
keys = [p[0] for p in pairs]
i = bisect.bisect_left(keys, target)Быстрая проверка
Рассуждайте о дубликатах и позициях вставки.
Повторение: мастерство bisect
Теперь вы умеете находить позиции вставки, считать дубликаты и находить нижние и верхние границы за логарифмическое время. Прежде чем писать цикл, обратитесь к bisect. ✨
Часто задаваемые вопросы
Урок «bisect_left и bisect_right» бесплатный?
Да — полный текст урока «bisect_left и bisect_right» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 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 структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.
Сколько времени занимает урок «bisect_left и bisect_right»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Классический двоичный поиск без ошибок
- bisect_left и bisect_right
- Первое True: двоичный поиск по предикату
- Двоичный поиск по ответу