Как найти индекс, в который новый элемент можно вставить в отсортированный список и сохранить его отсортированным?

Ответ 1

Используйте bisect. Это не самый красивый API, но он именно то, что вам нужно.

Вы хотите использовать bisect.bisect, который возвращает именно то, что вы хотите.

Ответ 2

bisect - это модуль в стандартной библиотеке Python, который идеально подходит для этой задачи. Функция bisect в модуле bisect даст вам индекс точки вставки для значения.

Позвольте мне привести пример кода для bisect

from bisect import bisect
a = 132
b = [0, 10, 30, 60, 100, 150, 210, 280, 340, 480, 530]
print(bisect(b, a))

Результат будет 5, потому что список основан на 0, поэтому на самом деле это 6-я позиция.

Что вы можете знать, так это использовать результат для insert.

index = bisect(b, a)
b.insert(index, a)

или без промежуточной переменной

b.insert(bisect(b, a), a)

Теперь b будет [0, 10, 30, 60, 100, 132, 150, 210, 280, 340, 480, 530].

Ответ 3

Существует еще одна проблема с краевыми случаями. Например, предположим, что вы хотите выбрать элементы в вышеупомянутом b в диапазоне (a, c), и вы выбираете их с помощью

b[idx_a:idx_c]

тогда вам нужно подумать о том, где a, c являются фактически элементами b. Обратите внимание, что

bisect.bisect(b, 10)
bisect.bisect(b, 11)

оба будут давать индекс 2. Таким образом, если a=10 нам нужно понизить индекс на 1. К счастью, существует функция bisect.bisect_left, которая делает именно это, т.е. в нашем примере

bisect.bisect_left(b, 10)

дает 1.

В целом, левый индекс должен вычисляться с использованием bisect.bisect_left() и правого индекса bisect.bisect_right() (который совпадает с bisect.bisect()).