Работа с отсортированными списками иногда может быть немного сложной. Вам необходимо поддерживать порядок списка после каждой вставки и эффективно искать элементы внутри него. Бинарный поиск — мощный алгоритм поиска в отсортированном списке. Хотя реализовать его с нуля не так уж сложно, это может занять много времени. К счастью, Python предлагает модуль bisect, который значительно упрощает работу с отсортированными списками.

Что такое двоичный поиск?

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

Модуль bisect: упрощение операций с отсортированным списком

Хотя бинарный поиск эффективен, каждый раз писать реализацию может быть утомительно. Но что, если бы вы могли выполнять те же операции всего одной строкой кода? Именно здесь на помощь приходит модуль Python bisect. Являясь частью стандартной библиотеки Python, модуль bisect помогает поддерживать отсортированный список без необходимости сортировки его после каждой вставки. Это делается с помощью простого алгоритма деления пополам.

Модуль bisect предоставляет две ключевые функции: bisect и insort. Функция bisect находит индекс, в который должен быть вставлен элемент, чтобы сохранить сортировку списка, а функция insort вставляет элемент в список, сохраняя его отсортированный порядок.

Использование модуля bisect: практический пример

Начнем с импорта модуля:

import bisect

Пример 1. Вставка числа в отсортированный список

Предположим, у нас есть отсортированный список чисел:

data = [1, 3, 5, 6, 8]

Чтобы вставить новый номер, сохраняя при этом список отсортированным, просто используйте:

bisect.insort(data, 7)

после запуска этого кода данные будут выглядеть так:

[1, 3, 5, 6, 7, 8]

Пример 2. Поиск точки вставки

Что, если вы просто хотите узнать, куда будет вставлено число, не вставляя его на самом деле? Вы можете использовать функции bisect_left или bisect_right:

index = bisect.bisect_left(data, 4)
print(index)  # Output: 2

Это говорит нам о том, что цифру 4 следует вставить в индекс 2, чтобы список был отсортирован.

Пример 3. Поддержание отсортированного порядка в динамическом списке

Предположим, вы управляете динамически растущим списком и вам нужно вставлять элементы, сохраняя при этом его сортировку:

dynamic_data = []
for number in [10, 3, 7, 5, 8, 2]:
    bisect.insort(dynamic_data, number)
    print(dynamic_data)

Это будет выводить список на каждом этапе по мере вставки элементов:

[10]
[3, 10]
[3, 7, 10]
[3, 5, 7, 10]
[3, 5, 7, 8, 10]
[2, 3, 5, 7, 8, 10]

Пример 4. Использование bisect с пользовательскими объектами

Предположим, у вас есть список пользовательских объектов, например кортежей, и вы хотите вставить их на основе определенного критерия:

items = [(1, 'apple'), (3, 'cherry'), (5, 'date')]
bisect.insort(items, (2, 'banana'))
print(items)  # Output: [(1, 'apple'), (2, 'banana'), (3, 'cherry'), (5, 'date')]

Или вы можете вставить на основе второго элемента каждого кортежа:

items = [('a', 10), ('b', 20), ('c', 30)]
bisect.insort(items, ('d', 25), key=lambda x: x[1])
print(items)  # Output: [('a', 10), ('b', 20), ('d', 25), ('c', 30)]

bisect в действии: в поисках слов

Модуль bisect не ограничивается числами; это также может быть полезно для поиска в списках строк, кортежей, символов и т. д.
Например, чтобы найти слово в отсортированном списке:

def searchWord(dictionary, target):
    return bisect.bisect_left(dictionary, target)


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'guitar', 'happiness', 'ice', 'joke']
target = 'guitar'

Или, чтобы найти первое слово в группе слов с определенным префиксом:

def searchPrefix(dictionary, prefix):
    return bisect.bisect_left(dictionary, prefix), bisect.bisect_right(dictionary, prefix   'z') # adding 'z' to the prefix to get the last word starting with the prefix
# bisect_rigth function will be discussed in a moment


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'generator', 'genetic', 'genius', 'gentlemen', 'guitar', 'happiness', 'ice', 'joke']
prefix = 'gen'

Однако имейте в виду, что bisect_left возвращает индекс, куда должна быть вставлена ​​цель, а не то, существует ли цель в списке.

Варианты биссектрисы и сортировки

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

пополам под капотом

Мощь модуля bisect заключается в эффективной реализации алгоритма двоичного поиска. Например, когда вы вызываете bisect.bisect_left, функция по существу выполняет двоичный поиск в списке, чтобы определить правильную точку вставки для нового элемента.

Вот как это работает «под капотом»:

1. Инициализация: функция начинается с двух указателей, lo и hi, которые представляют нижнюю и верхнюю границы диапазона поиска в списке. Первоначально lo устанавливается в начало списка (индекс 0), а hi — в конец списка (индекс равен длине списка). Но вы также можете указать собственные значения lo и hi для поиска в определенном диапазоне списка.

2. Bisection: в цикле функция вычисляет среднюю точку (середину) между lo и hi. Затем он сравнивает значение в середине с целевым значением, которое вы хотите вставить.

3. Сравнение:

* If the target is less than or equal to the value at `mid`, the upper bound (`hi`) is moved to `mid`.
* If the target is greater, the lower bound (`lo`) is moved to `mid   1`.

1. Завершение: этот процесс продолжается, каждый раз сокращая диапазон поиска вдвое, пока lo не станет равным hi. На этом этапе lo (или hi) представляет правильный индекс, куда следует вставить цель, чтобы сохранить отсортированный порядок списка.

2. Вставка: для функции сортировки, как только правильный индекс найден с помощью bisect_left, цель вставляется в список в этой позиции.

Этот подход гарантирует эффективность процесса вставки с временной сложностью O(log n) для поиска и O(n) для вставки из-за операции сдвига списка. Это значительно эффективнее, чем сортировка списка после каждой вставки, особенно для больших наборов данных.

пример кода bisect_left:

    if lo 



пример кода insort_left:


def insort_left(a, x, lo=0, hi=None, *, key=None):

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)





  
  
  Заключение


Модуль bisect делает работу с отсортированными списками простой и эффективной. В следующий раз, когда вам понадобится выполнить бинарный поиск или вставить элементы в отсортированный список, вспомните модуль bisect и сэкономьте время и силы.