Вставить значение в отсортированный список, сохранив порядок и вернув позицию

Реализуйте функцию insert_sorted(arr, value).

Вход: arr — список целых чисел, отсортированный по неубыванию (может быть пустым, может содержать повторы и отрицательные числа); value — целое число.

Выход: целое число — индекс, по которому value оказалось в списке после вставки.

Дополнительное требование: список arr изменяется на месте — после вызова он должен содержать все прежние элементы плюс value и оставаться отсортированным по неубыванию. Новый список возвращать не нужно.

Правило для повторов: если в списке уже есть элементы, равные value, новое значение вставляется перед ними (самая левая допустимая позиция).

Краевые случаи:

• пустой список: value становится единственным элементом, возвращается 0;
• значение меньше всех: возвращается 0;
• значение больше всех: возвращается прежняя длина списка.

Требование по сложности: позицию нужно искать двоичным поиском за O(log n) сравнений. Линейный проход по списку в поисках места не подходит.

Модуль bisect использовать можно.

def insert_sorted(arr, value):
    # ваш код
    pass