前言
二分查找作為程序員的一項(xiàng)基本技能，是面試官最常使用來考察程序員基本素質(zhì)的算法之一，也是解決很多查找類題目的常用方法总棵，它可以達(dá)到O(log n)的時(shí)間復(fù)雜度运提。
一般而言蝗柔，當(dāng)一個(gè)題目出現(xiàn)以下特性時(shí)，你就應(yīng)該立即聯(lián)想到它可能需要使用二分查找：
- 待查找的數(shù)組有序或者部分有序
- 要求時(shí)間復(fù)雜度低于O(n)民泵，或者直接要求時(shí)間復(fù)雜度為O(log n)
二分查找有很多種變體癣丧，使用時(shí)需要注意查找條件，判斷條件和左右邊界的更新方式栈妆，三者配合不好就很容易出現(xiàn)死循環(huán)或者遺漏區(qū)域胁编，本篇中我們將介紹常見的幾種查找方式的模板代碼，包括：
- 標(biāo)準(zhǔn)的二分查找
- 二分查找左邊界
- 二分查找右邊界
- 二分查找左右邊界
- 二分查找極值點(diǎn)
本文的內(nèi)容來自于筆者個(gè)人的總結(jié)鳞尔，事實(shí)上二分查找有很多種等價(jià)的寫法嬉橙，本文只是列出了筆者認(rèn)為的最容易理解和記憶的方法。
標(biāo)準(zhǔn)二分查找
首先給出標(biāo)準(zhǔ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) >> 1);
if (nums[mid] == target) return mid;
else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
- 循環(huán)條件：
left <= right - 中間位置計(jì)算：
mid = left + ((right -left) >> 1) - 左邊界更新：
left = mid + 1 - 右邊界更新：
right = mid - 1 - 返回值：
mid / -1
這里有幾點(diǎn)需要注意：
我們的循環(huán)條件中包含了
left == right的情況寥假，則我們必須在每次循環(huán)中改變left和right的指向市框，以防止進(jìn)入死循環(huán)-
循環(huán)終止的條件包括：
- 找到了目標(biāo)值
-
left > right（這種情況發(fā)生于當(dāng)left, mid, right指向同一個(gè)數(shù)時(shí)，這個(gè)數(shù)還不是目標(biāo)值糕韧，則整個(gè)查找結(jié)束枫振。）
left + ((right -left) >> 1)其實(shí)和(left + right) / 2是等價(jià)的，這樣寫的目的一個(gè)是為了防止(left + right)出現(xiàn)溢出兔沃，一個(gè)是用右移操作替代除法提升性能蒋得。-
left + ((right -left) >> 1)對(duì)于目標(biāo)區(qū)域長(zhǎng)度為奇數(shù)而言，是處于正中間的乒疏，對(duì)于長(zhǎng)度為偶數(shù)而言额衙，是中間偏左的。因此左右邊界相遇時(shí)，只會(huì)是以下兩種情況：-
left/mid,right(left, mid 指向同一個(gè)數(shù)窍侧，right指向它的下一個(gè)數(shù)) -
left/mid/right（left, mid, right 指向同一個(gè)數(shù)）
-
即因?yàn)?code>mid對(duì)于長(zhǎng)度為偶數(shù)的區(qū)間總是偏左的县踢，所以當(dāng)區(qū)間長(zhǎng)度小于等于2時(shí)，mid 總是和 left在同一側(cè)伟件。
實(shí)戰(zhàn)1：Guess Number Higher or Lower
- leetcode 原題： https://leetcode.com/problems...
- 難度等級(jí)： Easy
We are playing the Guess Game. The game is as follows:
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
這題基本是可以直接照搬二分查找的硼啤，出題者沒有做任何包裝，我們直接使用標(biāo)準(zhǔn)二分查找：
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;
}
}
實(shí)戰(zhàn)2：Sqrt(x)
- leetcode 原題： https://leetcode.com/problems...
- 難度等級(jí)： Easy
Implement int sqrt(int x).
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.
這一題其實(shí)是二分查找的應(yīng)用斧账，乍一看好像和二分查找沒有關(guān)系谴返，但是我們可以用二分查找的思想快速定位到目標(biāo)值的平方根，屬于二分查找的一個(gè)簡(jiǎn)單運(yùn)用：
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
}
}
雖然是簡(jiǎn)單的題目咧织，但是還是要注意對(duì)溢出的處理嗓袱，例如我們使用 mid > x / mid 而不是 mid * mide > x 作為判斷條件，因?yàn)楹笳呖赡軙?huì)導(dǎo)致溢出习绢，這與我們使用 left + ((right - left) >> 1) 而不是 (left + right) / 2 作為mid的值是一個(gè)道理渠抹，這是因?yàn)?left + right 也可能溢出。
二分查找左邊界
利用二分法尋找左邊界是二分查找的一個(gè)變體闪萄，應(yīng)用它的題目常常有以下幾種特性之一：
- 數(shù)組有序梧却，但包含重復(fù)元素
- 數(shù)組部分有序，且不包含重復(fù)元素
- 數(shù)組部分有序败去，且包含重復(fù)元素
左邊界查找類型1
類型1包括了上面說的第一種放航，第二種情況。
既然要尋找左邊界为迈，搜索范圍就需要從右邊開始三椿，不斷往左邊收縮，也就是說即使我們找到了nums[mid] == target, 這個(gè)mid的位置也不一定就是最左側(cè)的那個(gè)邊界葫辐，我們還是要向左側(cè)查找搜锰，所以我們?cè)?code>nums[mid]偏大或者nums[mid]就等于目標(biāo)值的時(shí)候，繼續(xù)收縮右邊界耿战，算法模板如下：
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;
}
}
- 循環(huán)條件：
left < right - 中間位置計(jì)算：
mid = left + ((right -left) >> 1) - 左邊界更新：
left = mid + 1 - 右邊界更新：
right = mid - 返回值：
nums[left] == target ? left : -1
與標(biāo)準(zhǔn)的二分查找不同：
首先蛋叼，這里的右邊界的更新是right = mid，因?yàn)槲覀冃枰谡业侥繕?biāo)值后剂陡，繼續(xù)向左尋找左邊界狈涮。
其次，這里的循環(huán)條件是left < right鸭栖。
因?yàn)樵谧詈?code>left與right相鄰的時(shí)候歌馍，mid和left處于相同的位置(前面說過，mid偏左)晕鹊，則下一步松却，無論怎樣暴浦，left, mid, right都將指向同一個(gè)位置，如果此時(shí)循環(huán)的條件是left <= right晓锻，則我們需要再進(jìn)入一遍循環(huán)歌焦，此時(shí)，如果nums[mid] < target還好說砚哆，循環(huán)正常終止独撇；否則，我們會(huì)令right = mid躁锁，這樣并沒有改變left,mid,right的位置纷铣，將進(jìn)入死循環(huán)。
事實(shí)上灿里，我們只需要遍歷到left和right相鄰的情況就行了关炼，因?yàn)檫@一輪循環(huán)后，無論怎樣匣吊，left,mid,right都會(huì)指向同一個(gè)位置，而如果這個(gè)位置的值等于目標(biāo)值寸潦，則它就一定是最左側(cè)的目標(biāo)值色鸳；如果不等于目標(biāo)值，則說明沒有找到目標(biāo)值见转，這也就是為什么返回值是nums[left] == target ? left : -1命雀。
左邊界查找類型2
左邊界查找的第二種類型用于數(shù)組部分有序且包含重復(fù)元素的情況，這種條件下在我們向左收縮的時(shí)候斩箫，不能簡(jiǎn)單的令 right = mid吏砂，因?yàn)橛兄貜?fù)元素的存在，這會(huì)導(dǎo)致我們有可能遺漏掉一部分區(qū)域乘客，此時(shí)向左收縮只能采用比較保守的方式狐血，代碼模板如下：
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的唯一區(qū)別就在于對(duì)右側(cè)值的收縮更加保守。這種收縮方式可以有效地防止我們一下子跳過了目標(biāo)邊界從而導(dǎo)致了搜索區(qū)域的遺漏易核。
關(guān)于這種類型的例子匈织，可以看下面的實(shí)戰(zhàn)5。
實(shí)戰(zhàn)3：First Bad Version
- leetcode 原題： https://leetcode.com/problems...
- 難度等級(jí)： Easy
這道題的題目比較長(zhǎng)牡直，原題就不貼了缀匕，大意就是說：有這么一個(gè)數(shù)組：
[false, false, false, ..., fasle, true, true, ..., true]
求最左側(cè)的那個(gè)true的位置。
這就是一個(gè)典型的查找左邊界的問題：數(shù)組中包含重復(fù)元素碰逸，我們需要找到最左側(cè)邊界的位置乡小。直接使用二分查找左邊界的模板就行了：
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級(jí)別的題目饵史，簡(jiǎn)單的使用二分查找左邊界的模板就行了满钟，大家可以自行練習(xí)胜榔。
當(dāng)然，除了這種顯而易見的題目零远，對(duì)于一些變體苗分，我們也應(yīng)該要有能力去分辨，比如說這一題：LeetCode 658 牵辣。
實(shí)戰(zhàn)4：Find Minimum in Rotated Sorted Array
- leetcode 原題： https://leetcode.com/problems...
- 難度等級(jí)： Medium
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(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.
這一題看上去沒有重復(fù)元素摔癣，但是它也是查找左邊界的一種形式，即可以看做是查找旋轉(zhuǎn)到右側(cè)的部分的左邊界纬向，有了這個(gè)思想择浊，直接用二分查找左邊界的模板就行了：
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];
}
}
實(shí)戰(zhàn)5：Find Minimum in Rotated Sorted Array II
- leetcode 原題： https://leetcode.com/problems...
- 難度等級(jí)： Hard
這道題目和上面的實(shí)戰(zhàn)2類似，只是多了一個(gè)條件——數(shù)組中可能包含重復(fù)元素逾条，這就是我們之前說的二分查找左邊界的第二種類型琢岩，在這種情況下，我們只能采用保守收縮的方式师脂，以規(guī)避重復(fù)元素帶來的對(duì)于單調(diào)性的破壞：
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 位于旋轉(zhuǎn)點(diǎn)左側(cè)
left = mid + 1;
} else if (nums[mid] < nums[right]) { // mid 位于旋轉(zhuǎn)點(diǎn)右側(cè)
right = mid;
} else {
// 注意相等的時(shí)候的特殊處理担孔，因?yàn)橐蜃蟛檎易筮吔纾灾苯邮湛s右邊界
right--;
}
}
return nums[left];
}
}
二分查找右邊界
有了尋找左邊界的分析之后吃警，再來看尋找右邊界就容易很多了糕篇，畢竟左右兩種情況是對(duì)稱的嘛，關(guān)于使用場(chǎng)景這里就不再贅述了酌心，大家對(duì)稱著理解就好拌消。我們直接給出模板代碼：
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;
}
}
- 循環(huán)條件：
left < right - 中間位置計(jì)算：
mid = left + ((right -left) >> 1) + 1 - 左邊界更新：
left = mid - 右邊界更新：
right = mid - 1 - 返回值：
nums[right] == target ? right : -1
這里大部分和尋找左邊界是對(duì)稱著來寫的，唯獨(dú)有一點(diǎn)需要尤其注意——中間位置的計(jì)算變了安券，我們?cè)谀┪捕嗉恿?墩崩。這樣，無論對(duì)于奇數(shù)還是偶數(shù)侯勉，這個(gè)中間的位置都是偏右的鹦筹。
對(duì)于這個(gè)操作的理解，從對(duì)稱的角度看壳鹤，尋找左邊界的時(shí)候盛龄，中間位置是偏左的，那尋找右邊界的時(shí)候芳誓，中間位置就應(yīng)該偏右唄余舶，但是這顯然不是根本原因。根本原因是锹淌，在最后left和right相鄰時(shí)匿值，如果mid偏左，則left, mid指向同一個(gè)位置赂摆，right指向它們的下一個(gè)位置挟憔，在nums[left]已經(jīng)等于目標(biāo)值的情況下钟些，這三個(gè)位置的值都不會(huì)更新，從而進(jìn)入了死循環(huán)绊谭。所以我們應(yīng)該讓mid偏右政恍，這樣left就能向右移動(dòng)。這也就是為什么我們之前一直強(qiáng)調(diào)查找條件达传，判斷條件和左右邊界的更新方式三者之間需要配合使用篙耗。
右邊界的查找一般來說不會(huì)單獨(dú)使用，如有需要宪赶，一般是需要同時(shí)查找左右邊界宗弯。
二分查找左右邊界
前面我們介紹了左邊界和右邊界的查找，那么查找左右邊界就容易很多了——只要分別查找左邊界和右邊界就行了搂妻。
實(shí)戰(zhàn)6: Find First and Last Position of Element in Sorted Array
- leetcode 原題： https://leetcode.com/problems...
- 難度等級(jí)： Medium
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.
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].
這是一道特別標(biāo)準(zhǔn)的查找左右邊界的題目蒙保，我們只需要分別查找左邊界和右邊界就行了：
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-end
int 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-end
if (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;
}
}
二分查找極值
二分查找還有一種有趣的變體是二分查找極值點(diǎn)，之前我們使用nums[mid]去比較的時(shí)候欲主，常常是和給定的目標(biāo)值target比邓厕，或者和左右邊界比較，在二分查找極值點(diǎn)的應(yīng)用中扁瓢，我們是和相鄰元素去比邑狸，以完成某種單調(diào)性的檢測(cè)。關(guān)于這一點(diǎn)涤妒，我們直接來看一個(gè)例子就明白了。
實(shí)戰(zhàn)7：Find Peak Element
- leetcode 原題：https://leetcode.com/problems...
- 難度等級(jí)： Medium
A peak element is an element that is greater than its neighbors.
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] = -∞.
這一題的有趣之處在于他要求求一個(gè)局部極大值點(diǎn)赚哗，并且整個(gè)數(shù)組不包含重復(fù)元素她紫。所以整個(gè)數(shù)組甚至可以是無序的——你可能很難想象我們可以在一個(gè)無序的數(shù)組中直接使用二分查找，但是沒錯(cuò)屿储！我們確實(shí)可以這么干贿讹！誰要人家只要一個(gè)局部極大值即可呢。
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]够掠，這實(shí)際上是在判斷處于mid處的相鄰元素的單調(diào)性民褂。
總結(jié)
除了本文所介紹的二分查找的應(yīng)用方式，二分查找其實(shí)還有很多其他的變體和應(yīng)用疯潭，但它們基本上是循環(huán)條件赊堪，判斷條件，邊界更新方法的不同組合竖哩，例如哭廉，有的二分查找的循環(huán)條件可以是 while(left + 1 < right)，有的邊界的更新的條件需要依賴 nums[left], nums[mid], nums[mid+1], nums[right]四個(gè)值的相互關(guān)系相叁。
但是無論如何遵绰，代碼模板只是給大家一個(gè)理解問題的角度辽幌，生搬硬套總是不好的。實(shí)際應(yīng)用中椿访，我們只要記住循環(huán)條件乌企，判斷條件與邊界更新方法三者之間的配套使用就行了，基于這一點(diǎn)原則成玫，你就可以使用你自己習(xí)慣的方式來實(shí)現(xiàn)二分搜索加酵。
但是，如果你真的只是想應(yīng)付面試梁剔，我想下面這個(gè)表的總結(jié)應(yīng)該就差不多足夠用了：
| 查找方式 | 循環(huán)條件 | 左側(cè)更新 | 右側(cè)更新 | 中間點(diǎn)位置 | 返回值 |
|---|---|---|---|---|---|
| 標(biāo)準(zhǔn)二分查找 | 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 |
最后虽画，希望大家在理解二分查找的思想后都能夠?qū)懗鲞m合自己的搭配方式，共勉荣病！
(完)
文章轉(zhuǎn)自：https://segmentfault.com/a/1190000016825704
