#278. First Bad Version

題目描述

你是一個帶領團隊研發新產品的產品經理。
不幸的是，最新的產品版本沒有通過品質檢測。
由於每一個版本都是是繼承自前一次的版本，因此所有在不過關版本之後的版本也都會是不過關的。

假設你想在你有n個版本[1,2, ..., n]中找到第一個開始不過關的版本。

給你一個APIbool isBadVersion(version)可以幫你檢測版本是否是不過關的。實作一個函式來找到第一個不過關的版本，必須最小限度的使用API檢查版本。

限制條件

1 <= bad <= n <= 2^31-1
最小限度的使用API。

解題思路

Brute Force

最直覺的解決方式，從第一個開始檢查，直到遇到第一個錯誤版本。

public class Solution : VersionControl {
    public int FirstBadVersion(int n) {        
        for(int i=1;i<=n;i++){
			if(IsBadVersion(i)) return i;
		}
		return 0;
    }
}

複雜度分析：

時間複雜度：最糟糕的狀況要檢查所有版本，時間複雜度為O(n)。
空間複雜度：不用增加任何資料空間，空間複雜度為O(1)。

Binary Search

public class Solution : VersionControl {
    public int FirstBadVersion(int n) {        
        int leftVersion = 1;
        int rightVersion = n;
        while(leftVersion<=rightVersion){
            int mid = leftVersion/2+rightVersion/2;
            if(IsBadVersion(mid)){
                if(!IsBadVersion(mid-1)) return mid;
                else rightVersion = mid-1;
            }else{
                if(IsBadVersion(mid+1)) return mid+1;
                else leftVersion = mid+1;
            }            
        }
        return 0;        
    }
}

複雜度分析：

時間複雜度：二元搜尋每一次檢查可以排除掉一半的版本，時間複雜度為O(log n)。
空間複雜度：沒有任何會增加空間的資料結構，空間複雜度為O(1)。

學習重點

二元搜尋的應用。