-
折半查找法
鎖定
在計算機科學中，折半搜索（英語：half-interval search），也稱二分搜索（英語：binary search）、對數搜索（英語：logarithmic search），是一種在有序數組中查找某一特定元素的搜索算法。
- 中文名
- 折半查找法
- 外文名
- half-interval search
折半查找法程序介紹
折半查找法是效率較高的一種查找方法。假設有已經按照從小到大的順序排列好的五個整數a0~a4，要查找的數是X，其基本思想是： 設查找數據的範圍下限為l=0，上限為h=4，求中點m=（l+h）/2，用X與中點元素am比較，若X等於am，即找到，停止查找；否則，若X大於am，替換下限l=m+1，到下半段繼續查找；若X小於am，換上限h=m-1，到上半段繼續查找；如此重複前面的過程直到找到或者l>h為止。如果l>h，説明沒有此數，打印找不到信息，程序結束。
[2]
折半查找法優缺點
Bentley在他的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內寫出完全正確的二分搜索算法。問題的關鍵在於準確地制定各次查找範圍的邊界以及終止條件的確定，正確地歸納奇偶數的各種情況，其實整理後可以發現它的具體算法是很直觀的。
折半查找法的優點是比較次數少，查找速度快，平均性能好；
其缺點是要求待查表為有序表，且插入刪除困難。
因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。
折半查找法算法步驟描述
① 首先確定整個查找區間的中間位置 mid = (left + right)/2 。
② 用待查關鍵字值與中間位置的關鍵字值進行比較；若相等，則查找成功；若大於，則在後（右）半個區域繼續進行折半查找；若小於，則在前（左）半個區域繼續進行折半查找。
折半查找法基本算法實現
函數
bin_search(int A[],int n,int key){
int low,high,mid;
low = 0;
high = n-1;
while(low<=high)
{
mid =(low + high)/2;
if(A[mid]==key)return mid+1;
if(A[mid]<key){
low =mid + 1;
}
if(A[mid]>key){
high= mid - 1;
}
}
return -1;
}
C語言實現代碼
#include int main()
{
int a[11]={0,1,2,3,4,5,6,7,8,9,10},min=0,max=10,mid,n; //max為數列長度，a[0]作為第一個數組元素
printf("請輸入您要查找的數:\n");
scanf("%d",&n);
while(min+1!=max)
{
mid=(min+max)/2;
if (n>a[mid]) min=mid;
else if (n
else
{
printf("輸入的數在數列的第%d位\n",mid);
exit(0);
}
}
if(n==a[max])
{
max+=1;
printf("\n輸入的數在數列的第%d位\n",max);
}
else if(n==a[min])
{
min+=1;
printf("\n輸入的數在數列的第%d位\n",min);
}
else if(n!=a[mid])
printf("\n輸入的數不在數列中");
}
Dev-c++實現
#include
#include
void main()
{
int a[15]={1,2,3,4,5,6,7,8,9,10,11,12,13,15};
int n,m,top,bot,mid;
top=m=1; //此處修改top=0;m=1;
bot=14;
printf("please input a number:");
scanf("%d",&n);
while(top<=bot)
{
mid=(top+bot)/2;
if(n==a[mid])
{
printf("這是第%d個元素的值。\n",mid+1);
m=0;
break;
}
else if(n>a[mid])
top=mid+1;
else if(n
bot=mid-1;
}
if(m)
printf("無此數。\n");
system("PAUSE");
return 0;
}
- 參考資料
-
- 1. 基於折半查找算法的研究與改進 ．中國知網[引用日期2017-04-04]
- 2. 折半查找法 ．知網空間．2011-01-01[引用日期2014-01-09]
- 3. SIFT算法與折半查找法在產品表面缺陷檢測中的應用 ．中國知網[引用日期2017-04-04]
