面試前必知必會的二分查找及其變種
- 2020 年 12 月 8 日
- 筆記
需要更多演算法動圖詳解，可以微信搜索[袁廚的演算法小屋]
今天給大家帶來的是二分查找及其變種的總結，大家一定要看到最後呀，用心滿滿，廢話不多說，讓導演幫我們把鏡頭切到袁記菜館吧！
袁記菜館內。。。。
店小二：掌柜的，您進貨回來了呀，喲！今天您買這魚挺大呀！
袁廚：那是，這是我今天從咱們江邊買的，之前一直去菜市場買，那裡的老貴了，你猜猜我今天買的多少錢一條。
店小二：之前的魚，30個銅板一條，今天的我猜26個銅板。
袁廚：貴了。
店小二：還貴呀！那我猜20個銅板！
袁廚：還是貴了。
店小二：15個銅板。
袁廚：便宜了
店小二：18個銅板
袁廚：恭喜你猜對了
上面的例子就用到了我們的二分查找思想，如果你玩過類似的遊戲，那二分查找理解起來肯定很輕鬆啦，下面我們一起征服二分查找吧！
二分查找
二分查找也稱折半查找（Binary Search），是一種在有序數組中查找某一特定元素的搜索演算法。我們可以從定義可知，運用二分搜索的前提是數組必須是有序的，這裡需要注意的是，我們的輸入不一定是數組，也可以是數組中某一區間的起始位置和終止位置
通過上面二分查找的定義，我們知道了二分查找演算法的作用及要求，那麼該演算法的具體執行過程是怎樣的呢？
下面我們通過一個例子來幫助我們理解。我們需要在 nums 數組中，查詢元素 8 的索引
int[ ] nums = {1,3,4,5,6,8,12,14,16}; target = 8
（1）我們需要定義兩個指針分別指向數組的頭部及尾部，這是我們在整個數組中查詢的情況，當我們在數組
某一區間進行查詢時，可以輸入數組，起始位置，終止位置進行查詢。
（2）找出mid，該索引為 mid =（left + right）/ 2，但是這樣寫有可能溢出，所以我們需要改進一下寫成
mid = left +（right – left）/ 2 或者 left + ((right – left ) >> 1) 兩者作用是一樣的，都是為了找到兩指針的中
間索引，使用位運算的速度更快。那麼此時的 mid = 0 + (8-0) / 2 = 4
（3）此時我們的 mid = 4，nums[mid] = 6 < target,那麼我們需要移動我們的 left 指針，讓left = mid + 1，下次則可以在新的 left 和 right 區間內搜索目標值，下圖為移動前和移動後
（4）我們需要在 left 和 right 之間計算 mid 值，mid = 5 + （8 – 5）/ 2 = 6 然後將 nums[mid] 與 target 繼續比較，進而決定下次移動left 指針還是 right 指針，見下圖
（5）我們發現 nums[mid] > target，則需要移動我們的 right 指針， 則 right = mid – 1；則移動過後我們的 left 和 right 會重合，這裡是我們的一個重點大家需要注意一下，後面會對此做詳細敘述。
（6）我們需要在 left 和 right 之間繼續計算 mid 值，則 mid = 5 +（5 – 5）/ 2 = 5 ，見下圖，此時我們將 nums[mid] 和 target 比較，則發現兩值相等，返回 mid 即可 ，如果不相等則跳出循環，返回 -1。
二分查找的執行過程如下
1.從已經排好序的數組或區間中，取出中間位置的元素，將其與我們的目標值進行比較，判斷是否相等，如果相等
則返回。
2.如果 nums[mid] 和 target 不相等，則對 nums[mid] 和 target 值進行比較大小，通過比較結果決定是從 mid
的左半部分還是右半部分繼續搜索。如果 target > nums[mid] 則右半區間繼續進行搜索，即 left = mid + 1; 若
target < nums[mid] 則在左半區間繼續進行搜索，即 right = mid -1；
動圖解析
下面我們來看一下二分查找的程式碼，可以認真思考一下 if 語句的條件，每個都沒有簡寫。
public static int binarySearch(int[] nums,int target,int left, int right) {
//這裡需要注意，循環條件
while (left <= right) {
//這裡需要注意，計算mid
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
return mid;
}else if (nums[mid] < target) {
//這裡需要注意，移動左指針
left = mid + 1;
}else if (nums[mid] > target) {
//這裡需要注意，移動右指針
right = mid - 1;
}
}
//沒有找到該元素，返回 -1
return -1;
}
二分查找的思路及程式碼已經理解了，那麼我們來看一下實現時容易出錯的地方
1.計算 mid 時 ，不能使用 （left + right ）/ 2,否則有可能會導致溢出
2.while (left < = right) { } 注意括弧內為 left <= right ,而不是 left < right ，我們繼續回顧剛才的例子，如果我們設置條件為 left < right 則當我們執行到最後一步時，則我們的 left 和 right 重疊時，則會跳出循環，返回 -1，區間內不存在該元素，但是不是這樣的，我們的 left 和 right 此時指向的就是我們的目標元素 ，但是此時 left = right 跳出循環
3.left = mid + 1,right = mid – 1 而不是 left = mid 和 right = mid。我們思考一下這種情況,見下圖，當我們的target 元素為 16 時，然後我們此時 left = 7 ，right = 8，mid = left + (right – left) = 7 + (8-7) = 7，那如果設置 left = mid 的話，則會進入死循環，mid 值一直為7 。
下面我們來看一下二分查找的遞歸寫法
public static int binarySearch(int[] nums,int target,int left, int right) {
if (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] == target) {
//查找成功
return mid;
}else if (nums[mid] > target) {
//新的區間,左半區間
return binarySearch(nums,target,left,mid-1);
}else if (nums[mid] < target) {
//新的區間，右半區間
return binarySearch(nums,target,mid+1,right);
}
}
//不存在返回-1
return -1;
}
例題：
題目描述
給定一個排序數組和一個目標值，在數組中找到目標值，並返回其索引。如果目標值不存在於數組中，返回它將會被按順序插入的位置。
你可以假設數組中無重複元素。
示例 1:
輸入: [1,3,5,6], 5
輸出: 2
示例 2:
輸入: [1,3,5,6], 2
輸出: 1
示例 3:
輸入: [1,3,5,6], 7
輸出: 4
示例 4:
輸入: [1,3,5,6], 0
輸出: 0
題目解析
這個題目完全就和咱們的二分查找一樣，只不過有了一點改寫，那就是將咱們的返回值改成了 left，具體實現過程見下圖
class Solution {
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length-1;
//注意循環條件
while (left <= right) {
//求mid
int mid = left + ((right - left ) >> 1);
//查詢成功
if (target == nums[mid]) {
return mid;
//右區間
} else if (nums[mid] < target) {
left = mid + 1;
//左區間
} else if (nums[mid] > target) {
right = mid - 1;
}
}
//返回插入位置
return left;
}
}
二分查找變種一
上面我們說了如何使用二分查找在數組或區間里查出特定值的索引位置。但是我們剛才數組裡面都沒有重複值，查到返回即可，那麼我們思考一下下面這種情況
此時我們數組裡含有多個 5 ，我們查詢是否含有 5 可以很容易查到，但是我們想獲取第一個 5 和 最後一個 5 的位置應該怎麼實現呢？哦！我們可以使用遍歷，當查詢到第一個 5 時，我們設立一個指針進行定位，然後到達最後一個 5 時返回，這樣我們就能求的第一個和最後一個五了？因為我們這個文章的主題就是二分查找，我們可不可以用二分查找來實現呢？當然是可以的。
題目描述
給定一個按照升序排列的整數數組 nums，和一個目標值 target。找出給定目標值在數組中的開始位置和結束位置。
如果數組中不存在目標值 target，返回 [-1, -1]。
示例 1：
輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]
示例 2：
輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]
示例 3：
輸入：nums = [], target = 0
輸出：[-1,-1]
題目解析
這個題目很容易理解，我們在上面說了如何使用遍歷解決該題，但是這個題目的目的就是讓我們使用二分查找，我們來逐個分析，先找出目標元素的下邊界，那麼我們如何找到目標元素的下邊界呢？
我們來重點分析一下剛才二分查找中的這段程式碼
if (nums[mid] == target) {
return mid;
}else if (nums[mid] < target) {
//這裡需要注意，移動左指針
left = mid + 1;
}else if (nums[mid] > target) {
//這裡需要注意，移動右指針
right = mid - 1;
}
我們只需在這段程式碼中修改即可，我們再來剖析一下這塊程式碼，nums[mid] == target 時則返回，nums[mid] < target 時則移動左指針，在右區間進行查找， nums[mid] > target時則移動右指針，在左區間內進行查找。
那麼我們思考一下，如果此時我們的 nums[mid] = target ,但是我們不能確定 mid 是否為該目標數的左邊界，所以此時我們不可以返回下標。例如下面這種情況。
此時 mid = 4 ，nums[mid] = 5,但是此時的 mid 指向的並不是第一個 5，所以我們需要繼續查找 ，因為我們要找
的是數的下邊界，所以我們需要在 mid 的值的左區間繼續尋找 5 ，那我們應該怎麼做呢？我們只需在
target <= nums[mid] 時，讓 right = mid – 1即可，這樣我們就可以繼續在 mid 的左區間繼續找 5 。是不是聽著有點繞，我們通過下面這組圖進行描述。
其實原理很簡單，就是我們將小於和等於合併在一起處理，當 target <= nums[mid] 時，我們都移動右指針，也就是 right = mid -1，還有一個需要注意的就是，我們計算下邊界時最後的返回值為 left ，當上圖結束循環時，left = 3，right = 2，返回 left 剛好時我們的下邊界。我們來看一下求下邊界的具體執行過程。
動圖解析
計算下邊界程式碼
int lowerBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
//這裡需要注意，計算mid
int mid = left + ((right - left) >> 1);
if (target <= nums[mid]) {
//當目標值小於等於nums[mid]時，繼續在左區間檢索，找到第一個數
right = mid - 1;
}else if (target > nums[mid]) {
//目標值大於nums[mid]時，則在右區間繼續檢索，找到第一個等於目標值的數
left = mid + 1;
}
}
return left;
}
計算上邊界時算是和計算上邊界時條件相反，
計算下邊界時，當 target <= nums[mid] 時，right = mid -1；target > nums[mid] 時，left = mid + 1；
計算上邊界時，當 target < nums[mid] 時，right = mid -1; target >= nums[mid] 時 left = mid + 1;剛好和計算下邊界時條件相反，返回right。
計算上邊界程式碼
int upperBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
//求mid
int mid = left + ((right - left) >> 1);
//移動左指針情況
if (target >= nums[mid]) {
left = mid + 1;
//移動右指針情況
}else if (target < nums[mid]) {
right = mid - 1;
}
}
return left;
}
題目完整程式碼
class Solution {
public int[] searchRange (int[] nums, int target) {
int upper = upperBound(nums,target);
int low = lowerBound(nums,target);
//不存在情況
if (upper < low) {
return new int[]{-1,-1};
}
return new int[]{low,upper};
}
//計算下邊界
int lowerBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
//這裡需要注意，計算mid
int mid = left + ((right - left) >> 1);
if (target <= nums[mid]) {
//當目標值小於等於nums[mid]時，繼續在左區間檢索，找到第一個數
right = mid - 1;
}else if (target > nums[mid]) {
//目標值大於nums[mid]時，則在右區間繼續檢索，找到第一個等於目標值的數
left = mid + 1;
}
}
return left;
}
//計算上邊界
int upperBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (target >= nums[mid]) {
left = mid + 1;
}else if (target < nums[mid]) {
right = mid - 1;
}
}
return right;
}
}
二分查找變種二
我們在上面的變種中，描述了如何找出目標元素在數組中的上下邊界，然後我們下面來看一個新的變種，如何從數組或區間中找出第一個大於或最後一個小於目標元素的數的索引，例 nums = {1,3,5,5,6,6,8,9,11} 我們希望找出第一個大於 5的元素的索引，那我們需要返回 4 ，因為 5 的後面為 6，第一個 6 的索引為 4，如果希望找出最後一個小於 6 的元素，那我們則會返回 3 ，因為 6 的前面為 5 最後一個 5 的索引為 3。好啦題目我們已經了解，下面我們先來看一下如何在數組或區間中找出第一個大於目標元素的數吧。
找出第一個大於目標元素的數，大概有以下幾種情況
1.數組包含目標元素，找出在他後面的第一個元素
2.目標元素不在數組中，數組內的部分元素大於它，此時我們需要返回第一個大於他的元素
3.目標元素不在數組中，且數組中的所有元素都大於它，那麼我們此時返回數組的第一個元素即可
4.目標元素不在數組中，且數組中的所有元素都小於它，那麼我們此時沒有查詢到，返回 -1 即可。
既然我們已經分析完所有情況，那麼這個題目對咱們就沒有難度了，下面我們描述一下案例的執行過程
nums = {1,3,5,5,6,6,8,9,11} target = 7
上面的例子中，我們需要找出第一個大於 7 的數，那麼我們的程式是如何執行的呢？
上面的例子我們已經弄懂了，那麼我們看一下，當 target = 0時，程式應該怎麼執行呢？
OK!我們到這一步就能把這個變種給整的明明白白的了，下面我們看一哈程式程式碼吧，也是非常簡單的。
public static int lowBoundnum(int[] nums,int target,int left, int right) {
while (left <= right) {
//求中間值
int mid = left + ((right - left) >> 1);
//大於目標值的情況
if (nums[mid] > target) {
//返回 mid
if (mid == 0 || nums[mid-1] <= target) {
return mid;
}
else{
right = mid -1;
}
} else if (nums[mid] <= target){
left = mid + 1;
}
}
//所有元素都小於目標元素
return -1;
}
通過上面的例子我們應該可以完全理解了那個變種，下面我們繼續來看以下這種情況，那就是如何找到最後一個小於目標數的元素。還是上面那個例子
nums = {1,3,5,5,6,6,8,9,11} target = 7
查找最後一個小於目標數的元素，比如我們的目標數為 7 ，此時他前面的數為 6，最後一個 6 的索引為 5，此時我們返回 5 即可，如果目標數元素為 12，那麼我們最後一個元素為 11，仍小於目標數，那麼我們此時返回 8，即可。這個變種其實算是上面變種的相反情況，上面的會了，這個也完全可以搞定了，下面我們看一下程式碼吧。
public static int upperBoundnum(int[] nums,int target,int left, int right) {
while (left <= right) {
int mid = left + ((right - left) >> 1);
//小於目標值
if (nums[mid] < target) {
//看看是不是當前區間的最後一位，如果當前小於，後面一位大於，返回當前值即可
if (mid == right || nums[mid+1] >= target) {
return mid;
}
else{
left = mid + 1;
}
} else if (nums[mid] >= target){
right = mid - 1;
}
}
//沒有查詢到的情況
return -1;
}
哎嘛寫著寫著咋就那麼多了，太長了大家就不愛看啦，剩下的就放在下篇吧，咱們下篇見呀！
如果這篇文章對您有一丟丟幫助的話，或者是能感受到這篇文章的用心的話，那麼感謝您的點贊，在看，轉發呀，這樣我就滿血復活啦。
我是袁廚，一個酷愛用動圖解演算法的年輕人，一個酷愛做飯的程式設計師，一個想和你一起進步的小老弟。
