Определение позиции заданного числа в отсортированном массиве

Условие

Необходимо реализовать функцию, принимающую отсортированный список чисел и искомое значение. Функция должна вернуть индекс, по которому находится это значение в списке, либо -1, если значение отсутствует.

numbers = [1, 5, 7, 10, 20, 100]

def find_index(numbers, key):
    ...

Ответ

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

from bisect import bisect_left

def find_index(numbers, key):
    index = bisect_left(numbers, key)
    if index < len(numbers) and numbers[index] == key:
        return index
    return -1

Для [1, 5, 7, 10, 20, 100] число 10 находится по индексу 3, а 8 даст -1. Если есть дубликаты, возвращается первое вхождение. Пустой список обрабатывается без отдельной ветки.

Сложность поиска — O(log n), дополнительная память O(1). Отсортированность является предусловием: её полная проверка каждый раз стоила бы O(n).