First Bad Version — первая «плохая» версия в линейке

Условие

Версии нумеруются 1..n. Известно, что есть «плохая» версия, и все версии после неё — тоже плохие. Дан API isBadVersion(version) -> bool. Найдите минимальную плохую версию, минимизировав число вызовов API.

Решение

Это бинарный поиск по предикату «плохая ли версия» на пространстве [1..n]. Граница между «good ... good | bad ... bad» — искомая версия.

def firstBadVersion(self, n: int) -> int:
    lo, hi = 1, n
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if isBadVersion(mid):
            hi = mid          # граница не правее mid
        else:
            lo = mid + 1      # граница строго правее mid
    return lo

Сложность

• Вызовы API: O(log n).
• Время и память: те же.

Подводные камни

1. Переполнение mid. (lo + hi) / 2 для больших n — переполнение в C++/Java. Используйте lo + (hi - lo) / 2.
2. Не сдвигать hi = mid (а писать hi = mid - 1). При плохой версии в позиции mid сама mid может быть ответом — нельзя отбрасывать.
3. Цикл while lo <= hi. Тоже работает, но требует «отсечь» обе стороны и хранить результат отдельно. Полуоткрытый интервал чище.

Эталонный ответ

Бинарный поиск по предикату с полуоткрытым интервалом [lo, hi). O(log n) вызовов API.