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

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