大廠面試真題：第一個錯誤的代碼版本

代碼庫的版本號是從 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