程序介绍
折半查找法是效率较高的一种查找方法。假设有已经按照从小到大的顺序排列好的五个整数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，说明没有此数，打印找不到信息，程序结束。该方法是查找的范围不断缩小一半，所以查找效率较高。
优缺点
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]
low =mid + 1;
}
if(A[mid]>key){
high= mid - 1;
}
}
return -1;
}
C语言实现代码
#include int main()
{
int a={0,1,2,3,4,5,6,7,8,9,10},min=0,max=10,mid,n; //max为数列长度，a作为第一个数组元素
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={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;
}
