二分法（三种基本模版）
前言
二分查找作為程序員的一項基本技能，是面試官最常使用來考察程序員基本素質的算法之一，也是解決很多查找類題目的常用方法，它可以達到O(log n)的時間復雜度。
一般而言，當一個題目出現以下特性時，你就應該立即聯想到它可能需要使用二分查找：
二分查找有很多種變體，使用時需要注意查找條件，判斷條件和左右邊界的更新方式，三者配合不好就很容易出現死循環或者遺漏區域，本篇中我們將介紹常見的幾種查找方式的模板代碼，包括：
本文的內容來自于筆者個人的總結，事實上二分查找有很多種等價的寫法，本文只是列出了筆者認為的最容易理解和記憶的方法。
標準二分查找
首先給出標準二分查找的模板：
class BinarySearch {public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + ((right - left)/2);if (nums[mid] == target) return mid;else if (nums[mid] > target) {right = mid - 1;} else {left = mid + 1;}}return -1;} }- 循環條件：?left <= right
- 中間位置計算：?mid = left + ((right -left) >> 1)
- 左邊界更新：left = mid + 1
- 右邊界更新：?right = mid - 1
- 返回值：?mid / -1
循環終止的條件包括：
- 找到了目標值
- left > right?（這種情況發生于當left, mid, right指向同一個數時，這個數還不是目標值，則整個查找結束。）
left + ((right -left) >> 1)?對于目標區域長度為奇數而言，是處于正中間的，對于長度為偶數而言，是中間偏左的。因此左右邊界相遇時，只會是以下兩種情況：
- left/mid?,?right?(left, mid 指向同一個數，right指向它的下一個數)
- left/mid/right?（left, mid, right 指向同一個數）
即因為mid對于長度為偶數的區間總是偏左的，所以當區間長度小于等于2時，mid?總是和?left在同一側。
實戰1：Guess Number Higher or Lower
- leetcode 原題：?https://leetcode.com/problems...
- 難度等級： Easy
I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I'll tell you whether the number is higher or lower.
You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):
-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!
Example :
Input: n = 10, pick = 6
Output: 6
這題基本是可以直接照搬二分查找的，出題者沒有做任何包裝，我們直接使用標準二分查找：
public class Solution extends GuessGame {public int guessNumber(int n) {int left = 1;int right = n;while (left <= right) {int mid = left + ((right - left) >> 1);if (guess(mid) == 0) {return mid;} else if (guess(mid) == -1) {right = mid - 1;} else {left = mid + 1;}}return -1;} }實戰2：Sqrt(x)
- leetcode 原題：?https://leetcode.com/problems...
- 難度等級： Easy
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
這一題其實是二分查找的應用，乍一看好像和二分查找沒有關系，但是我們可以用二分查找的思想快速定位到目標值的平方根，屬于二分查找的一個簡單運用：
class Solution {public int mySqrt(int x) {if (x <= 1) return x;int left = 1;int right = x - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (mid > x / mid) {right = mid - 1;} else if (mid < x / mid) {if (mid + 1 > x / (mid + 1)) return mid;left = mid + 1;} else {return mid;}}return -1; // only for return a value} }雖然是簡單的題目，但是還是要注意對溢出的處理，例如我們使用?mid > x / mid?而不是?mid * mide > x?作為判斷條件，因為后者可能會導致溢出，這與我們使用?left + ((right - left) >> 1)?而不是?(left + right) / 2?作為mid的值是一個道理，這是因為?left + right?也可能溢出。
二分查找左邊界
利用二分法尋找左邊界是二分查找的一個變體，應用它的題目常常有以下幾種特性之一：
左邊界查找類型1
類型1包括了上面說的第一種，第二種情況。
既然要尋找左邊界，搜索范圍就需要從右邊開始，不斷往左邊收縮，也就是說即使我們找到了nums[mid] == target, 這個mid的位置也不一定就是最左側的那個邊界，我們還是要向左側查找，所以我們在nums[mid]偏大或者nums[mid]就等于目標值的時候，繼續收縮右邊界，算法模板如下：
class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else {right = mid;}}return nums[left] == target ? left : -1;} }- 循環條件：?left < right
- 中間位置計算：?mid = left + ((right -left) >> 1)
- 左邊界更新：left = mid + 1
- 右邊界更新：?right = mid
- 返回值：?nums[left] == target ? left : -1
與標準的二分查找不同：
首先，這里的右邊界的更新是right = mid，因為我們需要在找到目標值后，繼續向左尋找左邊界。
其次，這里的循環條件是left < right。
因為在最后left與right相鄰的時候，mid和left處于相同的位置(前面說過，mid偏左)，則下一步，無論怎樣，left,?mid,?right都將指向同一個位置，如果此時循環的條件是left <= right，則我們需要再進入一遍循環，此時，如果nums[mid] < target還好說，循環正常終止；否則，我們會令right = mid，這樣并沒有改變left,mid,right的位置，將進入死循環。
事實上，我們只需要遍歷到left和right相鄰的情況就行了，因為這一輪循環后，無論怎樣，left,mid,right都會指向同一個位置，而如果這個位置的值等于目標值，則它就一定是最左側的目標值；如果不等于目標值，則說明沒有找到目標值，這也就是為什么返回值是nums[left] == target ? left : -1。
左邊界查找類型2
左邊界查找的第二種類型用于數組部分有序且包含重復元素的情況，這種條件下在我們向左收縮的時候，不能簡單的令?right = mid，因為有重復元素的存在，這會導致我們有可能遺漏掉一部分區域，此時向左收縮只能采用比較保守的方式，代碼模板如下：
class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid;} else {right--;}}return nums[left] == target ? left : -1;} }它與類型1的唯一區別就在于對右側值的收縮更加保守。這種收縮方式可以有效地防止我們一下子跳過了目標邊界從而導致了搜索區域的遺漏。
關于這種類型的例子，可以看下面的實戰5。
實戰3：First Bad Version
- leetcode 原題：?https://leetcode.com/problems...
- 難度等級： Easy
這道題的題目比較長，原題就不貼了，大意就是說：有這么一個數組：
[false, false, false, ..., fasle, true, true, ..., true]求最左側的那個true的位置。
這就是一個典型的查找左邊界的問題：數組中包含重復元素，我們需要找到最左側邊界的位置。直接使用二分查找左邊界的模板就行了：
public class Solution extends VersionControl {public int firstBadVersion(int n) {int left = 0;int right = n - 1;while (left < right) {int mid = left + ((right - left) >> 1);if (!isBadVersion(mid + 1)) {left = mid + 1;} else {right = mid;}}return isBadVersion(left + 1) ? left + 1 : -1;} }與之類似的例子還有：LeetCode 744?等，都是Easy級別的題目，簡單的使用二分查找左邊界的模板就行了，大家可以自行練習。
當然，除了這種顯而易見的題目，對于一些變體，我們也應該要有能力去分辨，比如說這一題：LeetCode 658?。
實戰4：Find Minimum in Rotated Sorted Array
- leetcode 原題：?https://leetcode.com/problems...
- 難度等級： Medium
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
Find the minimum element.
You may assume no duplicate exists in the array.
這一題看上去沒有重復元素，但是它也是查找左邊界的一種形式，即可以看做是查找旋轉到右側的部分的左邊界，有了這個思想，直接用二分查找左邊界的模板就行了：
class Solution {public int findMin(int[] nums) {if (nums.length == 1) return nums[0];int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + ((right - left) >> 1);if (nums[mid] > nums[nums.length - 1]) {left = mid + 1;} else {right = mid;}}return nums[left];} }實戰5：Find Minimum in Rotated Sorted Array II
- leetcode 原題：?https://leetcode.com/problems...
- 難度等級： Hard
這道題目和上面的實戰2類似，只是多了一個條件——數組中可能包含重復元素，這就是我們之前說的二分查找左邊界的第二種類型，在這種情況下，我們只能采用保守收縮的方式，以規避重復元素帶來的對于單調性的破壞：
class Solution {public int findMin(int[] nums) {if (nums.length == 1) return nums[0];int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + ((right - left) >> 1);if (nums[mid] > nums[right]) { // mid 位于旋轉點左側left = mid + 1;} else if (nums[mid] < nums[right]) { // mid 位于旋轉點右側right = mid;} else { // 注意相等的時候的特殊處理，因為要向左查找左邊界，所以直接收縮右邊界right--;}}return nums[left];} }二分查找右邊界
有了尋找左邊界的分析之后，再來看尋找右邊界就容易很多了，畢竟左右兩種情況是對稱的嘛，關于使用場景這里就不再贅述了，大家對稱著理解就好。我們直接給出模板代碼：
class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + ((right - left) >> 1) + 1;if (nums[mid] > target) {right = mid - 1;} else {left = mid;}}return nums[right] == target ? right : -1;} }- 循環條件：?left < right
- 中間位置計算：?mid = left + ((right -left) >> 1) + 1
- 左邊界更新：left = mid
- 右邊界更新：?right = mid - 1
- 返回值：?nums[right] == target ? right : -1
這里大部分和尋找左邊界是對稱著來寫的，唯獨有一點需要尤其注意——中間位置的計算變了，我們在末尾多加了1。這樣，無論對于奇數還是偶數，這個中間的位置都是偏右的。
對于這個操作的理解，從對稱的角度看，尋找左邊界的時候，中間位置是偏左的，那尋找右邊界的時候，中間位置就應該偏右唄，但是這顯然不是根本原因。根本原因是，在最后left和right相鄰時，如果mid偏左，則left,?mid指向同一個位置，right指向它們的下一個位置，在nums[left]已經等于目標值的情況下，這三個位置的值都不會更新，從而進入了死循環。所以我們應該讓mid偏右，這樣left就能向右移動。這也就是為什么我們之前一直強調查找條件，判斷條件和左右邊界的更新方式三者之間需要配合使用。
右邊界的查找一般來說不會單獨使用，如有需要，一般是需要同時查找左右邊界。
二分查找左右邊界
前面我們介紹了左邊界和右邊界的查找，那么查找左右邊界就容易很多了——只要分別查找左邊界和右邊界就行了。
實戰6: Find First and Last Position of Element in Sorted Array
- leetcode 原題：?https://leetcode.com/problems...
- 難度等級： Medium
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
這是一道特別標準的查找左右邊界的題目，我們只需要分別查找左邊界和右邊界就行了：
class Solution {public int[] searchRange(int[] nums, int target) {int[] res = new int[]{-1, -1};if(nums == null || nums.length == 0) return res;// find the left-endint left = 0;int right = nums.length - 1;while (left < right) {int mid = left + ((right - left) >> 1);if (nums[mid] < target) {left = mid + 1;} else {right = mid;}}res[0] = nums[left] == target ? left : -1;// find right-endif (res[0] != -1) {if (left == nums.length - 1 || nums[left + 1] != target) {res[1] = left;} else {right = nums.length - 1;while (left < right) {int mid = left + ((right - left) >> 1) + 1;if (nums[mid] > target) {right = mid - 1;} else {left = mid;}}res[1] = right;}}return res;} }二分查找極值
二分查找還有一種有趣的變體是二分查找極值點，之前我們使用nums[mid]去比較的時候，常常是和給定的目標值target比，或者和左右邊界比較，在二分查找極值點的應用中，我們是和相鄰元素去比，以完成某種單調性的檢測。關于這一點，我們直接來看一個例子就明白了。
實戰7：Find Peak Element
- leetcode 原題：https://leetcode.com/problems...
- 難度等級： Medium
Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that nums[-1] = nums[n] = -∞.
這一題的有趣之處在于他要求求一個局部極大值點，并且整個數組不包含重復元素。所以整個數組甚至可以是無序的——你可能很難想象我們可以在一個無序的數組中直接使用二分查找，但是沒錯！我們確實可以這么干！誰要人家只要一個局部極大值即可呢。
class Solution {public int findPeakElement(int[] nums) {int left = 0;int right = nums.length - 1;while (left < right) {int mid = left + ((right - left) >> 1);if (nums[mid] < nums[mid + 1]) {left = mid + 1;} else {right = mid;}}return left;} }這里尤其注意我們的判斷條件nums[mid] < nums[mid + 1]，這實際上是在判斷處于mid處的相鄰元素的單調性。
總結
除了本文所介紹的二分查找的應用方式，二分查找其實還有很多其他的變體和應用，但它們基本上是循環條件，判斷條件，邊界更新方法的不同組合，例如，有的二分查找的循環條件可以是?while(left + 1 < right)，有的邊界的更新的條件需要依賴?nums[left],?nums[mid],?nums[mid+1],?nums[right]四個值的相互關系。
但是無論如何，代碼模板只是給大家一個理解問題的角度，生搬硬套總是不好的。實際應用中，我們只要記住循環條件，判斷條件與邊界更新方法三者之間的配套使用就行了，基于這一點原則，你就可以使用你自己習慣的方式來實現二分搜索。
但是，如果你真的只是想應付面試，我想下面這個表的總結應該就差不多足夠用了：
| 標準二分查找 | left <= right | left = mid - 1 | right = mid + 1 | (left + right) / 2 | -1 / mid |
| 二分找左邊界 | left < right | left = mid - 1 | right = mid | (left + right) / 2 | -1 / left |
| 二分找右邊界 | left < right | left = mid | right = mid - 1 | (left + right) / 2 + 1 | -1 / right |
最后，希望大家在理解二分查找的思想后都能夠寫出適合自己的搭配方式，共勉！
(完)
總結
以上是生活随笔為你收集整理的二分法（三种基本模版）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： RStudio（You‘re using
- 下一篇： 回溯法（其实是递归）