大厂面试真题：第一个错误的代码版本

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

在线评测地址：领扣刷题官网

样例

n = 5:

    isBadVersion(3) -> false
    isBadVersion(5) -> true
    isBadVersion(4) -> true

因此可以确定第四个版本是第一个错误版本。

算法：二分
假设第k个版本为第一个错误版本，那么1---n个版本分为1---k-1为正确版本，k---n为错误版本，
我们需要以尽量少的次数去找到这个k，显然我们如果一个个找过去的平均复杂度是O(n)
那么我们可以考虑用二分来找到这个k,二分的复杂度为O(logn)

• 二分[1,n]这个区间

• 判断isBadVersion（mid）

  • 如果为false 说明第一个错误版本在mid的右边，令 left = mid
  • 反之则在mid左边，令 right = mid
• 缩小判断范围，当left+1>=right的时候结束二分
• 最后再次判断下isBadVersion（left）,如果是错误版本的话返回left,反之返回right

复杂度分析

• 时间复杂度O(logn)

  • 二分的时间复杂度

• 空间复杂度O(1)

  • 无需额外空间

public class Solution {
    /**
     * @param n: An integer
     * @return: An integer which is the first bad version.
     */
    public int findFirstBadVersion(int n) {
        int left = 1, right = n; // 左右边界
        while (left + 1 < right){
            int mid = left + (right - left) / 2;
            // 判断mid是否为正确版本，如果是的话，那么说明错误版本在mid的右边，反之则在左边
            if (SVNRepo.isBadVersion(mid)){
                right = mid; // 向[left，mid]查找错误版本
            }
            else { 
                left = mid; // 向[mid，right]查找错误版本
            }
        }
        // 最后判断下left是否是错误版本
        if (SVNRepo.isBadVersion(left)){
            return left;
        }
        return right;
    }
}

更多题解参考：九章Solution