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

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

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

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].

Есть еще одна проблема с пограничными случаями. Например, предположим, что вы хотите выбрать элементы в вышеупомянутом 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()).