Сложность: easy
Вы являетесь менеджером продукта и в настоящее время возглавляете команду по разработке нового продукта. К сожалению, последняя версия вашего продукта не прошла проверку качества. Поскольку каждая версия разрабатывается на основе предыдущей версии, все версии, вышедшие после плохой версии, также оказываются плохими.
Предположим, у вас есть n версий [1, 2, ..., n], и вы хотите выяснить первую плохую версию, которая вызывает все последующие версии быть плохими.
Вам предоставлен API bool isBadVersion(version), который возвращает, является ли версия плохой. Реализуйте функцию для нахождения первой плохой версии. Вы должны минимизировать количество вызовов API.
Пример:
Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.
👨💻 Алгоритм:
1⃣Инициализация границ поиска:
Устанавливаем начальные значения левой и правой границ поиска: left = 1 и right = n.
2⃣Бинарный поиск:
Пока левая граница меньше правой, находим среднюю точку mid и проверяем, является ли она плохой версией с помощью isBadVersion(mid).
Если текущая версия mid плохая, смещаем правую границу к mid, иначе смещаем левую границу на mid + 1.
3⃣Возврат результата:
Когда левая граница станет равной правой, возвращаем left как индекс первой плохой версии.
😎 Решение:
class Solution:
def firstBadVersion(self, n: int) -> int:
left, right = 1, n
while left < right:
mid = left + (right - left) // 2
if isBadVersion(mid):
right = mid
else:
left = mid + 1
return left
Ставь 👍 и забирай 📚 Базу знаний