代码库的版本号是从 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;     } } 

更多题解参考

大佬有話說 (0)