第一个错误的代码版本

时间：2022-08-21 05:36:00
题目描述：代码库的版本号是从 1 到 n 的整数。某一天，有人提交了错误版本的代码，因此造成自身及之后版本的代码在单元测试中均出错。请找出第一个错误的版本号。你可以通过 isBadVersion 的接口来判断版本号 version 是否在单元测试中出错，具体接口详情和调用方法请见代码的注释部分。


样例：


给出 n=5

调用isBadVersion(3)，得到false

调用isBadVersion(5)，得到true

调用isBadVersion(4)，得到true

此时我们可以断定4是第一个错误的版本号


非常简单的二分法，如果你已经熟练掌握了之前的内容，那么这道题实在是太easy了。设置两个指针left&right，求取中值mid，根据题目描述，如果检测出mid所指向的代码有问题，那么一定是mid或者mid之前的代码是第一个错误的版本；如果检测出mid没问题，那么第一个错误的版本就一定在mid之后，然后按照二分法的套路不断逼近第一个错误版本的index就行。（有关二分法的常见套路，出门左转，见我之前的博客）


代码如下：

#class SVNRepo:
#    @classmethod
#    def isBadVersion(cls, id)
#        # Run unit tests to check whether verison `id` is a bad version
#        # return true if unit tests passed else false.
# You can use SVNRepo.isBadVersion(10) to check whether version 10 is a 
# bad version.
class Solution:
    """
    @param n: An integers.
    @return: An integer which is the first bad version.
    """
    def findFirstBadVersion(self, n):
        left, right = 1, n
        while left < right:
            mid = (left + right) // 2
            # 运行有误，则错误代码版本在此或在此之前
            if SVNRepo.isBadVersion(mid) is True:
                right = mid
            # 运行无误，则错误代码版本在此之后
            elif SVNRepo.isBadVersion(mid) is False:
                left = mid + 1
        # 这里，return right是一样的
        return left
        # write your code here

需要注意的是最后一行return right也是一样的，因为最后left和right一定是指向同一个元素的。这是有关二分法的边界问题，不明白的话，一定要想清楚。



标签：

相关文章