你是產(chǎn)品經(jīng)理，目前正在帶領(lǐng)一個(gè)團(tuán)隊(duì)開發(fā)新的產(chǎn)品。
不幸的是，你的產(chǎn)品的最新版本沒有通過質(zhì)量檢測(cè)。
由于每個(gè)版本都是基于之前的版本開發(fā)的，所以錯(cuò)誤的版本之后的所有版本都是錯(cuò)的。

假設(shè)你有 n 個(gè)版本 [1, 2, ..., n]，你想找出導(dǎo)致之后所有版本出錯(cuò)的第一個(gè)錯(cuò)誤的版本。

你可以通過調(diào)用 bool isBadVersion(version) 接口來判斷版本號(hào) version 是否在單元測(cè)試中出錯(cuò)。
實(shí)現(xiàn)一個(gè)函數(shù)來查找第一個(gè)錯(cuò)誤的版本。你應(yīng)該盡量減少對(duì)調(diào)用 API 的次數(shù)。

示例:

給定 n = 5，并且 version = 4 是第一個(gè)錯(cuò)誤的版本。

調(diào)用 isBadVersion(3) -> false
調(diào)用 isBadVersion(5) -> true
調(diào)用 isBadVersion(4) -> true

所以，4 是第一個(gè)錯(cuò)誤的版本。 

解法一：

這道題的意思是有一系列版本，其中有一個(gè)版本是錯(cuò)誤的，而且后面的版本都是錯(cuò)誤的，然后給了一個(gè) API 接口可以用來判定當(dāng)前版本是否錯(cuò)誤，讓我們盡可能少的調(diào)用這個(gè) API，找出第一個(gè)壞版本。理解了題意之后，可以很快想到使用二分查找法。因?yàn)檎_版本和錯(cuò)誤版本之間有個(gè)邊界，所以我們就用二分法來找這個(gè)邊界，對(duì) middle 值調(diào)用 API 接口，如果是錯(cuò)誤版本，說明邊界在左邊，則把 middle 賦值給 hight，如果是正確版本，則說明邊界在右邊，則把 middle + 1賦給 low，最后返回 low 即可。需要注意的是，如果 low 和 hight 都特別大的話，那么 low + hight 可能會(huì)溢出，我們的處理方法就是把計(jì)算中間值變成 low + (hight - low )/2，以此來避免溢出問題。

    public int firstBadVersion(int n) {

        int low = 1, high = n;

        while (low < high) {

            int middle = low + (high - low) / 2;

            if (isBadVersion(middle)) {
                high = middle;
            } else {
                low = middle + 1;
            }
        }
        return low;
    }