你還不懂二分查找？那是你沒看這篇文章

? 前言

關于 二分查找，我之前寫過一篇簡單的文章，但是因為太過于簡單，加上各方面考慮不周，所以自己利用空余時間，重新看了書籍，閱讀了大量博客，重新寫了一篇 進階版😎

二分法的思想十分容易理解，但還是很多人對二分感到很苦惱，很困惑，可能是因為 二分的邊界 很難掌握，也許是判斷條件難寫…

二分法細節確實比較多，但是真正理解之后，是可以有一個通用模板的，根本不需要考慮到底是開區間還是閉區間，加一還是減一還是不加減，更不需要打補丁，

然而，很幸運，你找到了這篇文章，仔細看下去，這篇文章將帶你 學透二分 ！！！

Let’s get it！

? 二分查找

🏬小故事：

小明和冰冰在玩猜數字的游戲；

游戲規則：在1~100中，冰冰隨便想一個數字，讓小明來猜，游戲開始啦！

假設小明從1開始依次往上猜，猜測程序會是這樣：

（這是簡單查找，更準確的說法是傻找，每次猜測都只能排除一個數字，如果冰冰想的數字是 99，小明得猜 99次 才能猜到！）

于是另一種更佳的猜法，小明直接從 50 開始猜，

小了，但排除了一半的數字！至此，小明知道1～50都小了，接下來，小明猜 75，

大了，那余下的數字又排除了一半！使用二分查找時，小明猜測的是中間的數字，從而每次都將余下的數字排除一半，接下來，小明猜 63（50和75中間的數字），

這就是二分查找，小明學習了第一種演算法！每次猜測排除的數字個數如下

不管冰冰心里想的是哪個數字，小明在 7 次之內都能猜到，因為每次猜測都將排除很多數字！

🤔思考：

假設你要在字典中查找一個單詞，而該字典包含 240000 個單詞，你認為每種查找最多需要多少步？

如果要查找的單詞位于字典末尾，使用簡單查找將需要 240000 步，

使用二分查找時，每次排除一半單詞，直到最后只剩下一個單詞，

因此，使用二分查找只需 18 步——少多了！一般而言，對于包含n個元素的串列，用二分查找最多需要 log?n 步，而簡單查找最多需要 n 步，

（以上示例出自《演算法圖解》）

? 總結二分

我自己總結了會運用到 二分查找 的幾種情況，

我們先假設陣列是升序排列，再給你一個數target，

如下圖：

🐱?🐉思路：進階版一和進階版二應該盡量用同一種方法解決，而不需要考慮太多不一樣的細節，而在我的思路中，進階版一二三四都是同一個套路，Don’t Blink

🎊 基礎版

首先你需要知道最基礎版應該怎么寫，二分法的思想其實很簡單，就是先取中間的數，然后和target比較，如果小了就往右找，大了就往左找，然后再取中間數，如此回圈，直到中間沒有數了，

思路我相信大家都能理解，但是在寫法上，實際上還有一個 雙指標 的思想，也就是我們需要left和right兩個指標，然后不斷調整兩個指標的位置，最終得到答案，

下面我們通過一個例子來幫助我們理解，

我們需要在 nums 陣列中，查詢元素 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；

🐱?💻動圖決議：

📄代碼示例

廢話不多說，我們看一下代碼

int binarySearch(int *nums, int sz, int target)
{
	int left = 0;//左下標
	int right = sz - 1;//右下標

	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 {
			//移動右下標
			right = mid - 1;
		}
	}
	//沒有找到該元素，回傳-1
	return -1;
}

int main()
{
	int target = 8;//我們要查找的數字

	int nums[] = { 1,3,4,5,6,8,12,14,16 };

	int sz = sizeof(nums) / sizeof(nums[0]);

	int ret = binarySearch(nums, sz, target);

	if (-1 == ret) {
		printf("nums陣列中不存在traget\n");
	} else {
		printf("找到了,下標是%d,數字是%d\n", ret, target);
	}
	return 0;
	
}

運行結果：

🐱?🚀決議：

我相信大家可能看過其他版本，比如所謂的開區間版本，但是我告訴大家，沒有必要去看去記這么多版本，你只要會一種就能解萬題！！！，而我建議大家就寫上面這種，

這種也叫閉區間版本，每一個數都會搜索到，需要注意的幾個點

1、right初始是sz-1，很好理解，因為這是陣列右邊界下標

2、while里面是left <= right，也好理解，因為我們每個數都要搜索，當left = right時，我們當然要進里面再判斷一下

3、區間范圍縮小時，left=mid+1或者right=mid-1，也好理解，因為nums[mid]已經不是我們要找的數，所以范圍需要加一或者減一

二分查找的思路及代碼已經理解了，那么我們來看一下實作時容易出錯的地方

1、計算 mid 時 ，不能使用 （left + right ）/ 2,否則有可能會導致溢位

2、while (left < = right) 注意括號內為left <= right ,而不是 left < right ；

我們繼續回顧剛才的例子，如果我們設定條件為 left < right 則當我們執行到最后一步時，則我們的 left 和 right 重疊時，則會跳出回圈，回傳 -1，區間內不存在該元素，但其實不是這樣的！

我們的 left 和 right 此時指向的就是我們的目標元素 ，但是此時 left = right 跳出回圈（因為我們的while回圈條件是：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 ，

之所以要推薦閉區間版本，是因為它最符合我們的直觀邏輯，而且它是對稱的，是把left和right一視同仁，而不會像有的版本left需要加一，但是right卻不需要減一，

🎊 進階版一

有了基礎版，那么如何在基礎版的代碼上進行升級呢？

先來看問題：

找到等于target的左邊界（陣列中可能有多個數都等于target），找不到回傳-1

說實話，如果是第一次碰到這個問題，還真不一定能找到最優解！

第一個直觀感受可能是我找到mid后，在往左一個一個地看，看看哪里是邊界，但是這樣，時間復雜度可能退化成o(n)！

其實還是應該用二分的思想找，關鍵在于nums[mid] == target時候的處理，

📄代碼示例

int binarySearch(int* nums, int sz, int target)
{
	int left = 0;//左下標
	int right = sz - 1;//右下標
	
	int flag = -1;
	while (left <= right)
	{
		//計算mid
		int mid = left + ((right - left) >> 1);

		if (nums[mid] == target) {
			flag = mid;
			right = mid - 1;
		}
		else if (nums[mid] < target) {
			//移動左下標
			left = mid + 1;
		}
		else {
			//移動右下標
			right = mid - 1;
		}
	}
	//沒有找到該元素，回傳-1
	return flag;
}

🤔決議：

這里的一個技巧就是當arr[mid] == target時，因為要找左邊界，我們把right=mid-1，也就是改變右邊界從而縮小范圍，

這時候其實存在兩種情況，要么答案已經是flag(左邊界)，[left,right]里面已經沒有答案，while再也不會更新flag，最侄訓傳flag是正確的，

要么flag還不是最終答案，那么答案就會在[left,right]里面，而在while中，我們總能找到它從而更新flag，最侄訓傳flag也是正確的，

這里我們額外定義了一個flag表示結果，這一步是整個解法的精髓，相對于很多其他教程在考慮到底是回傳left還是left+1還是right還是right-1，直接定義一個flag要好理解得多，

🙋?這里也要注意幾點：

1、flag一定是符合條件的，比如在這里，我們只有當arr[mid] == target的時候，我們才會更新flag，

2、flag會隨著搜索范圍減小越來越接近答案，當搜索結束時，flag就是答案，

3、如果一次都沒有更新flag，說明整個陣列里沒有滿足條件的數，flag應該為-1，也就是初始值，

🎊 進階版二

先看問題：

找到等于target的右邊界（陣列中可能有多個數都等于target），找不到回傳-1

理解了上面的進階版一，我相信這個問題都不需要我解釋，直接看代碼就行，

📄代碼示例

int binarySearch(int* nums, int sz, int target)
{
	int left = 0;//左下標
	int right = sz - 1;//右下標
	int flag = -1;
	while (left <= right)
	{
		//計算mid
		int mid = left + ((right - left) >> 1);

		if (nums[mid] == target) {
			flag = mid;
			left = mid + 1;
		}
		else if (nums[mid] < target) {
			//移動左下標
			left = mid + 1;
		}
		else {
			//移動右下標
			right = mid - 1;
		}
	}
	//沒有找到該元素，回傳-1
	return flag;
}

同樣，在進階版三和進階版四中，只需要考慮什么時候更新flag；

🎊 進階版三

先看問題：

找到小于target的最大值，找不到回傳-1

因為要找的數是小于target的，所以應該在arr[mid] < target時更新flag；

📄代碼示例

int binarySearch(int* nums, int sz, int target)
{
	int left = 0;
	int right = sz - 1;
	int flag = -1;
	while (left <= right)
	{

		int mid = left + ((right - left) >> 1);
		if (nums[mid] < target) {
			flag = mid;
			left = mid + 1;
		}
		else {
			right = mid - 1;
		}
	}
	return flag;
}

🎊 進階版四

先看問題：

找到大于target的最小值，找不到回傳-1

因為要找的數是大于target的，所以應該在arr[mid] > target時更新flag；

📄代碼示例

int binarySearch(int* nums, int sz, int target)
{
	int left = 0;
	int right = sz - 1;
	int flag = -1;
	while (left <= right)
	{

		int mid = left + ((right - left) >> 1);
		if (nums[mid] < target) {
			left = mid + 1;
		}
		else {
			flag = mid;
			right = mid - 1;
		}
	}
	return flag;
}

🐱?🏍 推薦例題

光看不練，豈不是白給嗎？下面這幾道題個別還是有點難度，仔細理解，干就完事了！

📄例題一：leetcode35. 搜索插入位置

📄例題二：leetcode34. 在排序陣列中查找元素的第一個和最后一個位置

📄例題三：leetcode33. 搜索旋轉排序陣列

📄例題四：leetcode81. 搜索旋轉排序陣列 II

📄例題五：leetcode153. 尋找旋轉排序陣列中的最小值

🎃 結語

其實我看了網上很多講二分查找的文章，包括公眾號和知乎的，我認為，講得都比較不是很通俗易懂；

像有些文章還介紹了：第一種寫法、第二種寫法、什么左閉右閉、左閉右開…

我看了都覺得頭暈😵

給大家推薦Linux之父Linus采訪的一個視頻：采訪Linux之父Linus Torvalds：Linux背后的思想

大致意思就是說：所有的教科書都會告訴我們要分情況，但是我們要從另外一個角度看，如果兩種情況可以統一，而一個邏輯統一的代碼才是好代碼！

🌟你知道的越多，你不知道越多，我們下期見！