leetcode with python:278. First Bad Version

题目:

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%)

那我们下题见