704. 二分查找
給定一個 n 個元素有序的（升序）整型數(shù)組 nums 和一個目標(biāo)值 target ，寫一個函數(shù)搜索 nums 中的 target，如果目標(biāo)值存在返回下標(biāo)，否則返回 -1。

示例 1:

輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現(xiàn)在 nums 中并且下標(biāo)為 4
示例 2:

輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此返回 -1

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/binary-search
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解題思路及方法

經(jīng)典不多逼逼。

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        int res = -1;
        while (left <= right) {
            res = (left + right) / 2;
            if (nums[res] == target) return res;
            if (nums[res] < target) left = res + 1;
            if (nums[res] > target) right = res - 1;
        }
        
        return -1;
    }
}

結(jié)果如下：

278. 第一個錯誤的版本
你是產(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ù)。

示例 1：

輸入：n = 5, bad = 4
輸出：4
解釋：
調(diào)用 isBadVersion(3) -> false
調(diào)用 isBadVersion(5) -> true
調(diào)用 isBadVersion(4) -> true
所以，4 是第一個錯誤的版本。
示例 2：

輸入：n = 1, bad = 1
輸出：1

來源：力扣（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)載請注明出處。

解題思路及方法

這道題有點意思，雖然用了二分查找，但其實是找二分查找的轉(zhuǎn)折點。二分的時候?qū)懛☉?yīng)該是mid = left + (right - left) / 2，這樣可以防止越界。然后判斷isBadVersion(mid)，如果為真，說明當(dāng)前mid是錯誤版本，第一個錯誤版本應(yīng)該在左邊，包含mid本身，所以right = mid；否則為假，說明第一個錯誤版本在mid右邊，不包括mid，left = mid + 1。循環(huán)的終止條件是left = right，即找到答案，隨便返回即可。
這個二分法講的挺好：鏈接

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return left;
    }
}

結(jié)果如下：