二分查找法作為一種常見的查找方法，將原本是線性時間提升到了對數時間范圍，大大縮短了搜索時間，具有很大的應用場景，而在LeetCode中，要運用二分搜索法來解的題目也有很多，但是實際上二分查找法的查找目標有很多種，而且在細節寫法也有一些變化。之前有網友留言希望博主能針對二分查找法的具體寫法做個總結，博主由于之前一直很忙，一直拖著沒寫，為了樹立博主言出必行的正面形象，不能再無限制的拖下去了，那么今天就來做個了斷吧，總結寫起來~ (以下內容均為博主自己的總結，并不權威，權當參考，歡迎各位大神們留言討論指正)

根據查找的目標不同，博主將二分查找法主要分為以下五類：

?

第一類： 需查找和目標值完全相等的數

這是最簡單的一類，也是我們最開始學二分查找法需要解決的問題，比如我們有數組[2, 4, 5, 6, 9]，target = 6，那么我們可以寫出二分查找法的代碼如下:

int find(vector<int>& nums, int target) 
{int left = 0, right = nums.size();while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] == target) return mid;else if (nums[mid] < target) left = mid + 1;else right = mid - 1;}return -1;
}

會返回3，也就是target的在數組中的位置。注意二分查找法的寫法并不唯一，主要可以變動地方有四處：

第一處是right的初始化，可以寫成 nums.size() 或者 nums.size() - 1

第二處是left和right的關系，可以寫成 left < right 或者 left <= right

第三處是更新right的賦值，可以寫成 right = mid 或者 right = mid - 1

第四處是最后返回值，可以返回left，right，或right - 1

但是這些不同的寫法并不能隨機的組合，像博主的那種寫法，若right初始化為了nums.size()，那么就必須用left < right，而最后的right的賦值必須用 right = mid。但是如果我們right初始化為 nums.size() - 1，那么就必須用 left <= right，并且right的賦值要寫成 right = mid - 1，不然就會出錯。所以博主的建議是選擇一套自己喜歡的寫法，并且記住，實在不行就帶簡單的例子來一步一步執行，確定正確的寫法也行。

第一類應用實例：

Intersection of Two Arrays

?

?

第二類： 查找第一個不小于目標值的數( >= )，可變形為查找最后一個小于目標值的數??

這是比較常見的一類，因為我們要查找的目標值不一定會在數組中出現，也有可能是跟目標值相等的數在數組中并不唯一，而是有多個，那么這種情況下nums[mid] == target這條判斷語句就沒有必要存在。比如在數組[2, 4, 5, 6, 9]中查找數字3，就會返回數字4的位置；在數組[0, 1, 1, 1, 1]中查找數字1，就會返回第一個數字1的位置。我們可以使用如下代碼：

int find(vector<int>& nums, int target) 
{int left = 0, right = nums.size();while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < target) left = mid + 1;else right = mid;}return right;
}

最后我們需要返回的位置就是right指針指向的地方。在C++的STL中有專門的查找第一個不小于目標值的數的函數lower_bound，在博主的解法中也會時不時的用到這個函數。但是如果面試的時候人家不讓使用內置函數，那么我們只能老老實實寫上面這段二分查找的函數。

這一類可以輕松的變形為查找最后一個小于目標值的數，怎么變呢。我們已經找到了第一個不小于目標值的數，那么再往前退一位，返回right - 1，就是最后一個小于目標值的數。

第二類應用實例：

Heaters，?Arranging Coins，?Valid Perfect Square，Max Sum of Rectangle No Larger Than K，Russian Doll Envelopes

?

第二類變形應用：Valid Triangle Number

?

第三類： 查找第一個大于目標值的數，可變形為查找最后一個不大于目標值的數

這一類也比較常見，尤其是查找第一個大于目標值的數，在C++的STL也有專門的函數upper_bound，這里跟上面的那種情況的寫法上很相似，只需要添加一個等號，將之前的 nums[mid] < target 變成 nums[mid] <= target，就這一個小小的變化，其實直接就改變了搜索的方向，使得在數組中有很多跟目標值相同的數字存在的情況下，返回最后一個相同的數字的下一個位置。比如在數組[2, 4, 5, 6, 9]中查找數字3，還是返回數字4的位置，這跟上面那查找方式返回的結果相同，因為數字4在此數組中既是第一個不小于目標值3的數，也是第一個大于目標值3的數，所以make sense；在數組[0, 1, 1, 1, 1]中查找數字1，就會返回坐標5，通過對比返回的坐標和數組的長度，我們就知道是否存在這樣一個大于目標值的數。參見下面的代碼：

int find(vector<int>& nums, int target) 
{int left = 0, right = nums.size();while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] <= target) left = mid + 1;else right = mid;}return right;
}

這一類可以輕松的變形為查找最后一個不大于目標值的數，怎么變呢。我們已經找到了第一個大于目標值的數，那么再往前退一位，返回right - 1，就是最后一個不大于目標值的數。比如在數組[0, 1, 1, 1, 1]中查找數字1，就會返回最后一個數字1的位置4，這在有些情況下是需要這么做的。

第三類應用實例：

Kth Smallest Element in a Sorted Matrix

第三類變形應用示例：

Sqrt(x)

?

第四類： 用子函數當作判斷關系

這是最令博主頭疼的一類，而且通常情況下都很難。因為這里在二分查找法重要的比較大小的地方使用到了子函數，并不是之前三類中簡單的數字大小的比較，比如Split Array Largest Sum那道題中的解法一，就是根據是否能分割數組來確定下一步搜索的范圍。類似的還有Guess Number Higher or Lower這道題，是根據給定函數guess的返回值情況來確定搜索的范圍。對于這類題目，博主也很無奈，遇到了只能自求多福了。

第四類應用實例：

Split Array Largest Sum，?Guess Number Higher or Lower，Find K Closest Elements，Find K-th Smallest Pair Distance，Kth Smallest Number in Multiplication Table，Maximum Average Subarray II，Minimize Max Distance to Gas Station，Swim in Rising Water，Koko Eating Bananas

?

第五類： 其他

有些題目不屬于上述的四類，但是還是需要用到二分搜索法，比如這道?Find Peak Element，求的是數組的局部峰值。由于是求的峰值，需要跟相鄰的數字比較，那么 target 就不是一個固定的值，而且這道題的一定要注意的是right的初始化，一定要是nums.size() - 1，這是由于算出了mid后，nums[mid] 要和 nums[mid+1] 比較，如果right初始化為nums.size()的話，mid+1可能會越界，從而不能找到正確的值，同時 while 循環的終止條件必須是 left < right，不能有等號。

類似的還有一道?H-Index II，這道題的 target 也不是一個固定值，而是 len-mid，這就很意思了，跟上面的 nums[mid+1] 有異曲同工之妙，target 值都隨著 mid 值的變化而變化，這里的right的初始化，一定要是nums.size() - 1，而 while 循環的終止條件必須是 left <= right，這里又必須要有等號，是不是很頭大 -.-!!!

其實仔細分析的話，可以發現其實這跟第四類還是比較相似，目標值都不是固定的，第四類中雖然是用子函數來判斷關系，但大部分時候 mid 也會作為一個參數帶入子函數進行計算，這樣實際上最終算出來但目標值還是受 mid 的影響，但是 right 卻可以初始化為數組長度，循環條件也可以不帶等號，大家可以對比區別一下～

第五類應用實例：

Find Peak Element

H-Index II

?

綜上所述，博主大致將二分搜索法的應用場景分成了主要這五類，其中第二類和第三類還有各自的擴展。根據目前博主的經驗來看，第二類和第三類的應用場景最多，也是最重要的兩類。第一類，第四類，和第五類較少，其中第一類最簡單，第四類最難，遇到這類，博主也沒啥好建議，多多練習吧～

?

參考地址：LeetCode Binary Search Summary 二分搜索法小結