第一個錯誤的版本

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

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

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

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/first-bad-version/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：二分法

分別用low和high記錄第一個元素和最后一個元素，然后用二分法求解，求解過程如下：

• 用mid記錄中間位置，即low + (high - low) / 2，然后調(diào)用isBadVersion(mid)方法判斷當前版本是否是錯誤版本；

• 如果當前版本是錯誤版本且當前版本前面的一個版本(需要再次調(diào)用isBadVersion方法)也是錯誤版本，則將high重置為mid-1，然后進行下一輪處理；

• 如果當前版本是錯誤版本但是當前版本的前面一個版本不是錯誤版本，則當前版本即是第一個錯誤版本，返回當前版本；

• 如果當前版本不是錯誤版本，則將low重置為mid+1，然后進行下一輪處理。

• 循環(huán)終結(jié)的條件就是low大于high。

最后，如果沒有找到錯誤的版本，返回-1。

【每日寄語】 如果成功有捷徑，那條路一定是堅持。