你是產(chǎn)品經(jīng)理蚊丐，目前正在帶領(lǐng)一個團(tuán)隊(duì)開發(fā)新的產(chǎn)品。
不幸的是常拓，你的產(chǎn)品的最新版本沒有通過質(zhì)量檢測颈嚼。
由于每個版本都是基于之前的版本開發(fā)的，所以錯誤的版本之后的所有版本都是錯的灾而。
假設(shè)你有 n 個版本 [1, 2, ..., n]胡控，你想找出導(dǎo)致之后所有版本出錯的第一個錯誤的版本。
你可以通過調(diào)用 bool isBadVersion(version) 接口來判斷版本號 version 是否在單元測試中出錯旁趟。
實(shí)現(xiàn)一個函數(shù)來查找第一個錯誤的版本昼激。你應(yīng)該盡量減少對調(diào)用 API 的次數(shù)。
示例:
給定 n = 5锡搜，并且 version = 4 是第一個錯誤的版本橙困。
調(diào)用 isBadVersion(3) -> false
調(diào)用 isBadVersion(5) -> true
調(diào)用 isBadVersion(4) -> true
所以，4 是第一個錯誤的版本耕餐。
解法一：
這道題的意思是有一系列版本凡傅，其中有一個版本是錯誤的，而且后面的版本都是錯誤的肠缔，然后給了一個 API 接口可以用來判定當(dāng)前版本是否錯誤夏跷，讓我們盡可能少的調(diào)用這個 API哼转，找出第一個壞版本。理解了題意之后槽华，可以很快想到使用二分查找法释簿。因?yàn)檎_版本和錯誤版本之間有個邊界，所以我們就用二分法來找這個邊界硼莽，對 middle 值調(diào)用 API 接口庶溶，如果是錯誤版本，說明邊界在左邊懂鸵，則把 middle 賦值給 hight偏螺，如果是正確版本，則說明邊界在右邊匆光，則把 middle + 1賦給 low套像，最后返回 low 即可。需要注意的是终息，如果 low 和 hight 都特別大的話夺巩，那么 low + hight 可能會溢出，我們的處理方法就是把計(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;
}
