Задача: Первая плохая версия

Условие: производится разработка нового программного продукта, и на последней проверке было выявлено, что версия ПО не прошла проверку качества. Каждая следующая версия зависит от предыдущей, то есть если текущая версия не проходит проверки, то все последующие также не годны для какого-либо обслуживания. 

Предоставляется n - версий, нумерованных с единицы, необходимо найти первую неисправную версию ПО. 

Также дается интерфейс bool isBadVersion(version), который производит проверку на то, является ли проверяемая версия неисправной. Решить задачу необходимо за минимальное количество вызовов чекера. 

Пример:

Ввод: n = 5, bad = 4

Вывод: 4

Объяснение: 

call isBadVersion(3) -> false

call isBadVersion(5) -> true

call isBadVersion(4) -> true

4 - первая испорченная версия.

Ввод:

Вывод:

Решение:

Сложности:

• Временная сложность: O(logn)
• Пространственная сложность: O(1)

Код:

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        def search(low, high):
            while low < high:
                mid = (low + high) // 2
                if not isBadVersion(mid):
                   low = mid + 1
                else:
                    high = mid
            return low
        return search(1, n)