Bisect в Python: позиция вставки, повторы и проверка наличия

Если список уже отсортирован, bisect помогает найти место для нового значения. Он возвращает индекс вставки, поэтому результат ещё нужно проверить, если задача состоит в поиске существующего элемента. В практикуме Mentoring.digital разберём обе задачи на одном небольшом наборе.

Сначала проверьте порядок данных

Возьмём отсортированные баллы: 10, 20, 20, 40. В таком списке есть две позиции для вставки ещё одной двадцатки: перед существующими равными значениями и после них. bisect_left выбирает первую границу, bisect_right вторую.

from bisect import bisect_left, bisect_right, insort

scores = [10, 20, 20, 40]
left = bisect_left(scores, 20)
right = bisect_right(scores, 20)
print(left, right)  # 1 3
print(right - left)  # 2

insort(scores, 20)
print(scores)  # [10, 20, 20, 20, 40]

Разность правой и левой границ показывает количество равных значений в этом отсортированном наборе. insort добавляет элемент, сохраняя порядок. Исходный список при этом меняется.

Передавайте список, отсортированный по тому же правилу, которое используется при поиске. Если порядок нарушен, полученный индекс не становится надёжным ответом. Модуль не сортирует вход автоматически перед каждым поиском.

Как отличить найденное значение от места вставки

Для числа 25 функция тоже вернёт индекс. Но самого числа в списке нет. Поэтому для проверки наличия сначала убедитесь, что индекс находится внутри списка, а затем сравните значение.

def contains(sorted_values, value):
    index = bisect_left(sorted_values, value)
    return (index < len(sorted_values)
            and sorted_values[index] == value)

print(contains([10, 20, 20, 40], 20))  # True
print(contains([10, 20, 20, 40], 25))  # False
print(contains([], 20))  # False

Проверка границы нужна, например, когда искомое значение больше всех имеющихся: позиция вставки окажется равной длине списка. Пустой список тоже является нормальным случаем для этой функции.

Когда подход подходит задаче

Бинарный поиск позиции имеет логарифмическую сложность, но вставка в обычный список требует сдвига элементов и имеет линейную сложность. Поэтому insort не превращает частые вставки в дешёвую операцию. Если данные приходят большой пачкой, сравнивайте решение с отдельной сортировкой всей пачки.

Не меняйте один и тот же список из нескольких потоков без согласованной защиты. Документация bisect не даёт гарантии потокобезопасной совместной работы с изменяемой последовательностью.

Задание: напишите функцию, которая возвращает число баллов в диапазоне от low включительно до high не включительно. Подумайте, какие две левые границы понадобятся. Проверьте пустой список, одинаковые границы и повторяющиеся баллы.

Такую задачу удобно включить в практический курс Python, а выбор структуры данных разобрать с наставником по Python.