二分查找并不簡單，KMP發(fā)明人之一Knuth都說二分查找：思路很簡單唆垃，細節(jié)是魔鬼接校。二分查找里真正的坑不是整型溢出的bug，而是在于到底要給 mid 加一還是 減一糖耸，while 里到底用 <= 還是 <秘遏。

框架如下：

分析二分查找的一個技巧是：不要出現(xiàn)else，而是把所有情況用 else if 寫清楚蔬捷，這樣可以清楚地展現(xiàn)所有細節(jié)垄提。

其中 …… 的部分，就是可以能出現(xiàn)細節(jié)問題的地方周拐，當(dāng)你見到一個二分查找的代碼時铡俐，首先注意這幾個地方。

計算mid時需要防止溢出妥粟，代碼中 left + (right - left) / 2 就和 (left + right) / 2 的結(jié)果相同审丘，但是有效防止了 left 和 right 太大直接相加導(dǎo)致溢出。

一勾给、尋找一個數(shù)（基本的二分搜索）

這個場景是最簡單的滩报，搜索一個數(shù)，如果存在播急，返回其索引脓钾，否則返回-1。

此算法有什么缺陷桩警？

nums = [1,2,2,3]可训，target 為 2，此算法返回的索引是2捶枢。

但如果想得到 target 的左側(cè)邊界握截，即索引 1，或者target的右側(cè)邊界烂叔，索引為3谨胞，此算法不能直接處理，雖然可以找到一個target蒜鸡，然后向左或者向右線性搜索胯努，但這樣就難以保證二分查找對數(shù)級的復(fù)雜度了。

二逢防、尋找左側(cè)邊界的二分搜索

1. 為什么該算法能夠搜索左側(cè)邊界叶沛？

①當(dāng)nums[mid] > target 或 nums[mid] < target

????和普通二分查找一樣，還在逼近target

②當(dāng)nums[mid] == target

? ? 找到target胞四，但無法確定就是最左的target恬汁。

? ? 將當(dāng)前找到的target及其右側(cè)區(qū)間斬去：

? ? 1) 斬去target及右側(cè)后，左邊區(qū)間內(nèi)還有target：

????????相當(dāng)于回到 ① ，只是搜索區(qū)間變小了氓侧，又要重新逼近target脊另，直到nums[mid] 再次等于 target；不斷循環(huán)约巷，斬去右側(cè)偎痛，直到——

? ? 2) 斬去target及右側(cè)后，左邊區(qū)間內(nèi)不再有target：

? ? ? ? 說明剛才找到的 target 就是最左的target独郎，也就是right踩麦。

? ? ? ? 當(dāng)target > nums[right -1] 時，二分查找不斷舍棄左邊區(qū)間氓癌，最后left = right時退出while循環(huán)谓谦，這時的 right 就是一開始的 right;

? ? ? ? 反之，當(dāng)target < nums[0]時贪婉，二分查找不斷舍棄右邊區(qū)間反粥，最后right = left時退出while循環(huán)，這時的 left 就是一開始 0疲迂。

? ? ? ? 所以當(dāng)退出while循環(huán)才顿，如果是已經(jīng)找到target的情況，此時返回的 right = left = 找到最左target 時的 mid尤蒿。

2. 為什么 while 條件是 left? < right郑气，而不是 left <= right ？

注意到 right 是 nums.length 而不是 nums.length -1腰池，所以查找的區(qū)間應(yīng)該是 [left, right)尾组，否則右側(cè)數(shù)組會越界。

while(left < right) 終止條件是 left == right巩螃，此時搜索區(qū)間 [left, right) 為空演怎，所以可以正確終止匕争。

3. 為什么沒有返回 -1 的操作避乏？如果 nums 中不存在 target 這個值，怎么辦甘桑？

對于這個數(shù)組拍皮，算法會返回1，可以解讀為 nums 中小于 2 的元素有 1 個跑杭；

對于 nums = [2,3,5,7]铆帽，target = 1，算法會返回 0德谅，含義是 nums 中小于 1 的元素有 0 個爹橱；

對于 nums = [2,3,5,7]，target = 8窄做，算法會返回 4愧驱，含義是 nums 中小于 8 的元素有 4 個慰技。

所以簡單添加兩行代碼就能在正確的時候 return -1：

4. 為什么返回 left 而不是 right？

都是一樣的组砚，因為 while 終止的條件是 left == right吻商。

5.能不能把 right 變成 nums.length - 1， 也就是繼續(xù)使用兩邊都閉的「搜索區(qū)間」糟红？這樣就可以和基礎(chǔ)二分搜索統(tǒng)一起來艾帐。

當(dāng)然可以，只要「搜索區(qū)間」和搜索方式能夠避免漏掉元素盆偿，隨便怎么改都可以柒爸。

因為 right 初始化為 nums.length -1，那么 while的終止條件應(yīng)該是 left == right +1, 也就是while 條件應(yīng)該用 left <= right：

因為搜索區(qū)間是兩端都閉的事扭，且現(xiàn)在是搜索左側(cè)邊界揍鸟，所以 left 和 right 的更新邏輯如下：

返回 -1 的情況：

完整代碼如下：

這樣就和普通版二分搜索算法統(tǒng)一了，都是兩端都閉的「搜索區(qū)間」句旱。

三阳藻、尋找右側(cè)邊界的二分查找

同理：

四、總結(jié)

通過本文谈撒，你得到了：

1. 分析二分查找代碼時腥泥，不要出現(xiàn)else，全部展成 else if 方便理解

2. 注意「搜索區(qū)間」和 while 的終?條件啃匿，如果存在漏掉的元素蛔外，記得在最后檢查。

3. 如需定義左閉右開的「搜索區(qū)間」搜索左右邊界溯乒，只要在 nums[mid] == target時做修改即可夹厌，搜索右側(cè)時需要減一。

4. 如果將「搜索區(qū)間」全部統(tǒng)一成兩端都閉裆悄，好記矛纹，只要稍改 nums[mid] == target 條件處的代碼和返回的邏輯即可。