編程折半法
折半查找的演算法思想是將數列按有序化(遞增或遞減)排列，查找過程中採用跳躍式方式查找，即先以有序數列的中點位置為比較對象，如果要找的元素值小於該中點元素，則將待查序列縮小為左半部分，否則為右半部分。通過一次比較，將查找區間縮小一半。 折半查找是一種高效的查找方法。它可以明顯減少比較次數，提高查找效率。但是，折半查找的先決條件是查找表中的數據元素必須有序。參考程序，希望對你有所幫助！
#include<stdio.h>
void main()
{
int a[20],x,i,start,end;
printf("input 20 numbers:\n");
for(i=0;i<20;i++) scanf("%d",&a[i]);
printf("please enter the number:\n");
scanf("%d",&x);
for(start=0,end=19;start<=end;)
{
i=start+(end-start)/2;
if (x==a[i])
{
printf("%d",i+1);
getch();
return;
}
else if (x>a[i]) end = i-1;
else start=i+1;
}
}
㈡ 如何計算折半查找的平均查找長度
折半查找可以藉助於一個二叉樹來描述。
為了簡化討論，則把這棵樹近似看成滿二叉樹，設二叉樹的高度為h(h>1)
則，根據二叉樹的性質，它有最大節點數n=2^h-1，
則h=log2(n+1) (2是底數)。那麼二叉樹的第j層節點數為：2^(j-1)
假定每個元素的查找概率相等，則，pi=1/n (pi為第i個節點的查找概率)
那麼平均查找長度為 1/n*（1*2^0+2*2^1+3*2^2+……+j*2^(j-1)）
則經過化簡計算，得平均查找長度為：(（n+1）/n ) *log2(n+1)-1 (其中對數中的2為底數：即log以2為底（n+1)的對數）
注 : 當n很大時 ，可近似為 log2(n+1)-1
搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找。
而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜索演算法每一次比較都使搜索范圍縮小一半。
(2)編程折半法擴展閱讀：
假設有已經按照從小到大的順序排列好的五個整數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，說明沒有此數，列印找不到信息，程序結束。
用待查關鍵字值與中間位置的關鍵字值進行比較；若相等，則查找成功若大於，則在後（右）半個區域繼續進行折半查找若小於，則在前（左）半個區域繼續進行折半查找。
對確定的縮小區域再按折半公式，重復上述步驟。最後，得到結果：要麼查找成功， 要麼查找失敗。折半查找的存儲結構採用一維數組存放。