[数据结构与算法]LeetCode 278. First Bad Version - 二分查找（Binary Search）系列题15

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.

Example 1:

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.

Example 2:

Input: n = 1, bad = 1
Output: 1

Constraints:

• 1 <= bad <= n <= 231?- 1

题目很长，其实是一道最基本的二分查找法题。把版本号[left, right]从中间分成前后两个区间，判断中间版本号mid = (left + right) // 2， 如果中间版本号是Bad，右半区间肯定都是Bad可以排除则继续查找左半区间，否则继续查找右半区间。查找到最后，左边界left就是第一个Bad Version。

注：由于题目给限制条件是一定有一个Bad版本，所以最后左边界值left落在[1, n]，left就是第一Bad Version。

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        l, r = 1, n
        while l <= r:
            mid = l + (r - l) // 2
            if isBadVersion(mid):
                r = mid - 1
            else:
                l = mid + 1
                
        #由于题目一定会有一个bad version所以可以直接返回l
        return l