Определение первой дефектной версии программы с помощью бинарного поиска

Условие

Имеется упорядоченный массив версий программного обеспечения, в котором начиная с некоторой позиции все версии содержат ошибку. Функция is_bad_version() принимает номер версии и возвращает true, если данная версия неисправна. Реализуйте функцию, использующую алгоритм бинарного поиска, чтобы определить номер первой ошибочной версии в массиве.

Пример сигнатуры функции:

def first_bad_version(n: int) -> int:
    # ваш код

Ответ

Ищите первую True в монотонной последовательности версий 1…n. На плохой версии смещайте правую границу влево, на хорошей — левую вправо. Требуется O(log n) вызовов проверки.

Версия с -1 при отсутствии дефектов:

def first_bad_version(n):
    left, right = 1, n
    answer = -1
    while left <= right:
        middle = (left + right) // 2
        if is_bad_version(middle):
            answer = middle
            right = middle - 1
        else:
            left = middle + 1
    return answer

Сигнатура с n подразумевает номера подряд, а не произвольные строки версий. Для настоящего массива ищите по индексам и передавайте is_bad_version(versions[middle]). Без гарантии «все последующие тоже плохие» бинарный поиск применять нельзя.