目錄
一.前言
二.二分查找法
1.什么是二分查找法
2.如何用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是毫無疑問的，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/413424.html
標籤：其他
上一篇：＜2＞ 瀏覽檔案系統