用C語言實現二分查找算法
一.前言
假如今天我們需要在一個有序的數組中來尋找一個數的下標，就用"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是毫無疑問的。
總結
到此這篇關於c語言實現二分查找法的文章就介紹到這瞭,更多相關c語言二分查找法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！