題目:

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

給定一數n表示共有編號1~n的產品,其中有個bad version的產品,讓編號在其之後的產品也都變為bad version
找出那個bad vesion,題目有提供函數isBadVersion(x)來判斷一產品是否為bad version
函數中x是指產品編號,是bad version的話回傳True,反之回傳False

這題我們用二分搜來找出第一次出現bad version的點

# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:

class Solution:
    def firstBadVersion(self, n: int) -> int:
        if isBadVersion(1): #防範第1號產品就是bad version
            return 1
            
        l=1
        r=n
        while l+1!=r:
            mid=(l+r)//2
            if isBadVersion(mid):
                r=mid
            else:
                l=mid                
        return r

設好左右邊界(l,r),看編號中間值(mid)是否為bad version
若是則r下降至mid,否則l上升至mid
直到l,r相鄰
此時應該是一邊非bad version,一邊是bad version
所以此時的r是bad version的起始點
最後執行時間26ms(faster than 97.86%)

那我們下題見