思路

我相信對很多讀者朋友來說，編寫二分查找的算法代碼屬于玄學編程，雖然看起來很簡單，就是會出錯，要么會漏個等號，要么少加個 1。

不要氣餒，因為二分查找其實并不簡單。看看 Knuth 大佬（發明 KMP 算法的那位）怎么說的：

Although the basic idea of binary search is comparatively straightforward，

the details can be surprisingly tricky.。.

這句話可以這樣理解：思路很簡單，細節是魔鬼。

本文以問答的形式，探究幾個最常用的二分查找場景：尋找一個數、尋找左側邊界、尋找右側邊界。第一個場景是最簡單的算法形式，解決 這道題，后兩個場景就是本題。

而且，我們就是要深入細節，比如不等號是否應該帶等號，mid 是否應該加一等等。分析這些細節的差異以及出現這些差異的原因，保證你能靈活準確地寫出正確的二分查找算法。

零、二分查找框架

int binarySearch（int［］ nums， int target） {

int left = 0， right = 。..;

while（。..） {

int mid = （right + left） / 2;

if （nums［mid］ == target） {

。..

} else if （nums［mid］ 《 target） {

left = 。..

} else if （nums［mid］ 》 target） {

right = 。..

}

}

return 。..;

}

分析二分查找的一個技巧是：不要出現 else，而是把所有情況用 else if 寫清楚，這樣可以清楚地展現所有細節。本文都會使用 else if，旨在講清楚，讀者理解后可自行簡化。

其中 。.. 標記的部分，就是可能出現細節問題的地方，當你見到一個二分查找的代碼時，首先注意這幾個地方。后文用實例分析這些地方能有什么樣的變化。

另外聲明一下，計算 mid 時需要技巧防止溢出，即 mid=left+（right-left）/2。本文暫時忽略這個問題。

一、尋找一個數（基本的二分搜索）

這個場景是最簡單的，肯能也是大家最熟悉的，即搜索一個數，如果存在，返回其索引，否則返回 -1。

int binarySearch（int［］ nums， int target） {

int left = 0;

int right = nums.length - 1; // 注意

while（left 《= right） {

int mid = （right + left） / 2;

if（nums［mid］ == target）

return mid;

else if （nums［mid］ 《 target）

left = mid + 1; // 注意

else if （nums［mid］ 》 target）

right = mid - 1; // 注意

}

return -1;

}

1. 為什么 while 循環的條件中是 《=，而不是 《 ？

答：因為初始化 right 的賦值是 nums.length-1，即最后一個元素的索引，而不是 nums.length。

這二者可能出現在不同功能的二分查找中，區別是：前者相當于兩端都閉區間 ［left， right］，后者相當于左閉右開區間 ［left， right），因為索引大小為 nums.length 是越界的。

我們這個算法中使用的是前者 ［left， right］ 兩端都閉的區間。這個區間其實就是每次進行搜索的區間，我們不妨稱為「搜索區間」。

什么時候應該停止搜索呢？當然，找到了目標值的時候可以終止：

if（nums［mid］ == target）

return mid;

但如果沒找到，就需要 while 循環終止，然后返回 -1。那 while 循環什么時候應該終止？搜索區間為空的時候應該終止，意味著你沒得找了，就等于沒找到嘛。

while（left 《= right） 的終止條件是 left == right + 1，寫成區間的形式就是 ［right + 1， right］，或者帶個具體的數字進去 ［3， 2］，可見這時候搜索區間為空，因為沒有數字既大于等于 333 又小于等于 222 的吧。所以這時候 while 循環終止是正確的，直接返回 -1 即可。

while（left 《 right） 的終止條件是 left == right，寫成區間的形式就是 ［left， right］，或者帶個具體的數字進去 ［2， 2］，這時候搜索區間非空，還有一個數 2，但此時 while 循環終止了。也就是說這區間 ［2， 2］ 被漏掉了，索引 2 沒有被搜索，如果這時候直接返回 -1 就是錯誤的。

當然，如果你非要用 while（left 《 right） 也可以，我們已經知道了出錯的原因，就打個補丁好了：

//。..

while（left 《 right） {

// 。..

}

return nums［left］ == target ？ left ： -1;

2. 為什么 left = mid + 1，right = mid - 1？我看有的代碼是 right = mid 或者 left = mid，沒有這些加加減減，到底怎么回事，怎么判斷？

答：這也是二分查找的一個難點，不過只要你能理解前面的內容，就能夠很容易判斷。

剛才明確了「搜索區間」這個概念，而且本算法的搜索區間是兩端都閉的，即 ［left， right］。那么當我們發現索引 mid 不是要找的 target 時，如何確定下一步的搜索區間呢？

當然是 ［left， mid - 1］ 或者 ［mid + 1， right］ 對不對？因為 mid 已經搜索過，應該從搜索區間中去除。

3. 此算法有什么缺陷？

答：至此，你應該已經掌握了該算法的所有細節，以及這樣處理的原因。但是，這個算法存在局限性。

比如說給你有序數組 nums = ［1，2，2，2，3］，target = 2，此算法返回的索引是 2，沒錯。但是如果我想得到 target 的左側邊界，即索引 1，或者我想得到 target 的右側邊界，即索引 3，這樣的話此算法是無法處理的。

這樣的需求很常見。你也許會說，找到一個 target，然后向左或向右線性搜索不行嗎？可以，但是不好，因為這樣難以保證二分查找對數級的復雜度了。

我們后續的算法就來討論這兩種二分查找的算法。

二、尋找左側邊界的二分搜索

直接看代碼，其中的標記是需要注意的細節：

int left_bound（int［］ nums， int target） {

if （nums.length == 0） return -1;

int left = 0;

int right = nums.length; // 注意

while （left 《 right） { // 注意

int mid = （left + right） / 2;

if （nums［mid］ == target） {

right = mid;

} else if （nums［mid］ 《 target） {

left = mid + 1;

} else if （nums［mid］ 》 target） {

right = mid; // 注意

}

}

return left;

}

1. 為什么 while（left 《 right） 而不是 《= ？

答：用相同的方法分析，因為 right = nums.length 而不是 nums.length - 1 。因此每次循環的「搜索區間」是 ［left， right） 左閉右開。

while（left 《 right） 終止的條件是 left == right，此時搜索區間 ［left， left） 為空，所以可以正確終止。

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

答：因為要一步一步來，先理解一下這個「左側邊界」有什么特殊含義：

對于這個數組，算法會返回 1。這個 1 的含義可以這樣解讀：nums 中小于 2 的元素有 1 個。

比如對于有序數組 nums = ［2，3，5，7］， target = 1，算法會返回 0，含義是：nums 中小于 1 的元素有 0 個。

再比如說 nums 不變，target = 8，算法會返回 4，含義是：nums 中小于 8 的元素有 4 個。

綜上可以看出，函數的返回值（即 left 變量的值）取值區間是閉區間 ［0， nums.length］，所以我們簡單添加兩行代碼就能在正確的時候 return -1：

while （left 《 right） {

//。..

}

// target 比所有數都大

if （left == nums.length） return -1;

// 類似之前算法的處理方式

return nums［left］ == target ？ left ： -1;

3. 為什么 left = mid + 1，right = mid ？和之前的算法不一樣？

答：這個很好解釋，因為我們的「搜索區間」是 ［left， right） 左閉右開，所以當 nums［mid］ 被檢測之后，下一步的搜索區間應該去掉 mid 分割成兩個區間，即 ［left， mid） 或 ［mid + 1， right）。

4. 為什么該算法能夠搜索左側邊界？

答：關鍵在于對于 nums［mid］ == target 這種情況的處理：

if （nums［mid］ == target）

right = mid;

可見，找到 target 時不要立即返回，而是縮小「搜索區間」的上界 right，在區間 ［left， mid） 中繼續搜索，即不斷向左收縮，達到鎖定左側邊界的目的。

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

答：都是一樣的，因為 while 終止的條件是 left == right。

三、尋找右側邊界的二分查找

尋找右側邊界和尋找左側邊界的代碼差不多，只有兩處不同，已標注：

int right_bound（int［］ nums， int target） {

if （nums.length == 0） return -1;

int left = 0， right = nums.length;

while （left 《 right） {

int mid = （left + right） / 2;

if （nums［mid］ == target） {

left = mid + 1; // 注意

} else if （nums［mid］ 《 target） {

left = mid + 1;

} else if （nums［mid］ 》 target） {

right = mid;

}

}

return left - 1; // 注意

}

1. 為什么這個算法能夠找到右側邊界？

答：類似地，關鍵點還是這里：

if （nums［mid］ == target） {

left = mid + 1;

當 nums［mid］ == target 時，不要立即返回，而是增大「搜索區間」的下界 left，使得區間不斷向右收縮，達到鎖定右側邊界的目的。

2. 為什么最后返回 left - 1 而不像左側邊界的函數，返回 left？而且我覺得這里既然是搜索右側邊界，應該返回 right 才對。

答：首先，while 循環的終止條件是 left == right，所以 left 和 right 是一樣的，你非要體現右側的特點，返回 right - 1 好了。

至于為什么要減一，這是搜索右側邊界的一個特殊點，關鍵在這個條件判斷：

if （nums［mid］ == target） {

left = mid + 1;

// 這樣想： mid = left - 1

因為我們對 left 的更新必須是 left = mid + 1，就是說 while 循環結束時，nums［left］ 一定不等于 target 了，而 nums［left-1］ 可能是 target。更多精彩文章歡迎關注我的眾公號 labuladong。

至于為什么 left 的更新必須是 left = mid + 1，同左側邊界搜索，就不再贅述。

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

答：類似之前的左側邊界搜索，因為 while 的終止條件是 left == right，就是說 left 的取值范圍是 ［0， nums.length］，所以可以添加兩行代碼，正確地返回 ?1-1?1：

while （left 《 right） {

// 。..

}

if （left == 0） return -1;

return nums［left-1］ == target ？ （left-1） ： -1;

四、最后總結

來梳理一下這些細節差異的因果邏輯：

第一個，最基本的二分查找算法：

因為我們初始化 right = nums.length - 1

所以決定了我們的「搜索區間」是 ［left， right］

所以決定了 while （left 《= right）

同時也決定了 left = mid+1 和 right = mid-1

因為我們只需找到一個 target 的索引即可

所以當 nums［mid］ == target 時可以立即返回

第二個，尋找左側邊界的二分查找：

因為我們初始化 right = nums.length

所以決定了我們的「搜索區間」是 ［left， right）

所以決定了 while （left 《 right）

同時也決定了 left = mid + 1 和 right = mid

因為我們需找到 target 的最左側索引

所以當 nums［mid］ == target 時不要立即返回

而要收緊右側邊界以鎖定左側邊界

第三個，尋找右側邊界的二分查找：

因為我們初始化 right = nums.length

所以決定了我們的「搜索區間」是 ［left， right）

所以決定了 while （left 《 right）

同時也決定了 left = mid + 1 和 right = mid

因為我們需找到 target 的最右側索引

所以當 nums［mid］ == target 時不要立即返回

而要收緊左側邊界以鎖定右側邊界

又因為收緊左側邊界時必須 left = mid + 1

所以最后無論返回 left 還是 right，必須減一

如果以上內容你都能理解，那么恭喜你，二分查找算法的細節不過如此。

通過本文，你學會了：

分析二分查找代碼時，不要出現 else，全部展開成 else if 方便理解。

注意「搜索區間」和 while 的終止條件，如果存在漏掉的元素，記得在最后檢查。

如需要搜索左右邊界，只要在 nums［mid］ == target 時做修改即可。搜索右側時需要減一。

以后就算遇到其他的二分查找變形，運用這幾點技巧，也能保證你寫出正確的代碼。