一.前言

假如今天我們需要在一個有序的數組中來尋找一個數的下標，就用"1，2，3，4，5，6，7，8，9"這九個數組成的數組來說，假如我們想尋找'2'，那很簡單我們只用從小到大開始尋找，尋找兩次就完成了，但是我們想尋找'7'，我們繼續用從小到大挨個尋找，這就顯得有點慢并且耗時長還沒有效率，因此我們可以有一種全新的方法，二分查找法來解決這個問題。

二.二分查找法

1.什么是二分查找法

二分查找法，又叫做折半查找法，它是一種效率較高的查找方法。但是，折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。就用剛剛的數組來說，我們想尋找'7'，很簡單我們先用7和數組中間的數來比較大小，很明顯7大于，所以我們縮小范圍，從中間的右邊開始繼續取中間值，繼續尋找，直到找到位置，這樣一看找的次數少了很多，而且速度也快了不少。

2.如何用c語言來實現二分查找法

咱們來分析一下剛剛我說的找數字7的過程，首先我們需要數組的中間的數也就是中間數的下標值，那我們就需要直到數組第一個元素和最后一個元素的下標值，數組第一個元素下標值很明顯是0，我們把他定義成left；這個最后一個元素的下標值我們就需要利用sizeof來計算,我們把他定義成rigth。然后兩個相加，算出最中間的下標，我們把他定義為mid，和要找的數進行比較，假如大于要找的數那就從mid+1和right之間來繼續剛剛的循環，假如小于要找的數那我們就從left和mid-1之間尋找。就這樣一直循環，直到找到目標數為止。

代碼的實現如下

void Findnum(int* arr, int key,int sz)//arr為目標數組，key為需要查找的數,sz為數組元素的大小
{//二分查找
	int  left = 0;//左邊
	int right = sz-1;//右邊
	while (left <= right)
	{
		int mid = (right + left) / 2;
		if (arr[mid] > key)
		{//說明key在arr[mid]和left之間
			right = mid - 1;
		}
		else if (arr[mid] < key)
		{
			left = mid + 1;
		}
		else
		{
			printf("找到了，對應的下標為:%d\n", mid);
			break;
		}
	}
	if (left > right)
	{
		printf("找不到\n");
	}
}

最后運行

三.總結

關于上面的過程，我們不難發現二分查找法雖然很快，但是有兩個很明顯的缺點，一個是他實現的條件必須是一個有序的數列，另外一個是他只能一次性找一個數而不是多個，這就讓他有了很多局限性。二分查找有個很重要的特點，就是不會查找數列的全部元素，而查找的數據量其實正好符合元素的對數，正常情況下每次查找的元素都在一半一半地減少。所以二分查找的時間復雜度為

log2o是毫無疑問的。

總結