Модуль bisect - реализация алгоритма бинарного поиска

Алгоритм бинарного поиска

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

1. Определение значения элемента в середине структуры данных. Полученное значение сравнивается с нашим ключом.
2. Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй.
3. Затем вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом.
4. Процесс продолжается до тех пор, пока не будет найден элемент со значением ключа или не станет пустым интервал для поиска.

Сложность алгоритма O(log n), однако вставка в отсортированный список в Python имеет сложность O(n), необходимо это иметь в виду.

Реализация в модуле bisect

bisect.insort(list, elem, lo=0, hi=len(a)), или bisect.insort_right(list, elem, lo=0, hi=len(a)) — вставка элемента в отсортированный список, при этом elem располагается как можно правее (все элементы, равные ему, остаются слева). Параметры lo и hi (здесь и в других функциях) могут быть использованы для указания подмножества списка, которое нужно учитывать; по умолчанию используется весь список.

bisect.insort_left(list, elem, lo=0, hi=len(a)) — вставка элемента в отсортированный список, при этом elem располагается как можно левее (все элементы, равные ему, остаются справа).

bisect.bisect(list, elem, lo=0, hi=len(a)), или bisect.bisect_right(list, elem, lo=0, hi=len(a)) — поиск места для вставки элемента в отсортированный список, таким образом, чтобы elem располагался как можно правее.

bisect.bisect_left(list, elem, lo=0, hi=len(a)) — поиск места для вставки элемента в отсортированный список, таким образом, чтобы elem располагался как можно левее.

Примеры

Функция проверки наличия элемента в списке (аналог elem in l):

>>> from bisect import bisect_left
>>> def contains(l, elem):
...     index = bisect_left(l, elem)
...     if index < len(l):
...         return l[index] == elem
...     return False
...
>>> contains(list(range(1000)), -10)
False
>>> testlist = (1, 2, 3, 6, 8, 10, 15)
>>> contains(testlist, 10)
True
>>> contains(testlist, 0)
False
>>> contains(testlist, 20)
False

Поиск в таблице чисел. Пусть (баллы за экзамен) 90 и выше дают оценку ‘A’, 80-89 оцениваются как ‘B’, и так далее. Найдем оценки студентов по их баллам:

>>> def grade(score, breakpoints=(60, 70, 80, 90), grades='FDCBA'):
...     i = bisect(breakpoints, score)
...     return grades[i]
...
>>> [grade(score) for score in [33, 99, 77, 70, 89, 90, 100]]
['F', 'A', 'C', 'C', 'B', 'A', 'A']