Поиск отсортированного списка?

Ответ 1

bisect является частью стандартной библиотеки - это то, что вы ищете?

Ответ 2

Стоит отметить, что существует несколько высококачественных библиотек Python для поддержки отсортированного списка, который также реализует быстрый поиск: sortedcontainers и blist. Разумеется, это зависит от того, как часто вы вставляете/удаляете элементы из списка и нуждаетесь в поиске. Каждый из этих модулей предоставляет класс SortedList, который эффективно поддерживает элементы в порядке сортировки.

Из документации для SortedList:

L.bisect_left(value)
    Similar to the bisect module in the standard library, this returns
    an appropriate index to insert value in L. If value is already present
    in L, the insertion point will be before (to the left of) any existing
    entries.

L.bisect(value)
    Same as bisect_left.

L.bisect_right(value)
    Same as bisect_left, but if value is already present in L, the
    insertion point will be after (to the right of) any existing entries.

В обеих реализациях используется двоичный поиск, чтобы найти правильный индекс данного значения. Там сравнение производительности страница для выбора между двумя модулями.

Отказ от ответственности: я являюсь автором модуля sortedcontainers.