折半查找法是算法一种,可以被任何计算机语言使用。用C语言自然也可以实现。
1、定义:
在计算机科学中,折半搜索(英语:half-interval search),也称二分搜索(英语:binary search)、对数搜索(英语:logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。
搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
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,说明没有此数,打印找不到信息,程序结束。
3、C语言参考代码:
int bin_search(int A[],int n,int key){//在长度为n的数组A 中折半查找值为key的元素,并返回下标值。如果不存在则返回-1.
int low,high,mid
low = 0
high = n-1//初始low和high为数组的两端。
while(low<=high)
{
mid =(low + high)/2//查找中心点。
if(A[mid]==key)return mid//已找到,返回下标值。
if(A[mid]<key){//中点位置比key值小,以mid+1为新的下限值。
low =mid + 1
}
if(A[mid]>key){//中点位置比key值大,以mid-1为新的上限值。
high= mid - 1
}
}
return -1//未找到,返回-1.
}
折半查找的前提是已经对数据做好了排序,然后再折半查找例如排序后的数据是1 5 12 35 64 78 89 123 456
你要查找12,首先用12跟上面排好顺序的9个数中间那个比较(64),12<64,因此你查找的数据在前半部分,即
1 5 12 35 64,再用12跟前半部分中间那个数比较(12),这样找了2次就找到了
折半查找的目的是提高查找的效率 折半查找法也称为二分查找法,它充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。
【基本思想】
将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如果x<a[n/2],则我们只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。如果x>a[n/2],则我们只要在数组a的右半部继续搜索x。
二分搜索法的应用极其广泛,而且它的思想易于理解。第一个二分搜索算法早在1946 年就出现了,但是第一个完全正确的二分搜索算法直到1962年才出现。Bentley在他的著作《Writing Correct Programs》中写道,90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定,正确地归纳奇偶数的各种情况,其实整理后可以发现它的具体算法是很直观的。 刚开始的时候数组时排好顺序的:从小到大,或者从大到小。然后将这个数组折中,用中间的这个数和要查找的数比较大小,(例如:如果我从小到大,我将数组这种后,用中间的数和要查找的数比较,如果小
//参考代码如下:#include <stdio.h>
int main()
{
int i, j, n, k=0, isFound=0
int num[15] = {88,86,75,74,61,56,52,43,39,34,31,22,18,16,8} //测试数组
printf("请输出一个整数:\n")
scanf("%d", &n)
i = (int)15/2 //对折位移量
j = (int)15/2 //取数“指针”
while(k<2)
{
i = (int)i/2
if(i == 0) k++//i==0 即折半到无可再折时,仍有最后一次比较,故以k做计数
//若未相等,计算下一循环指针的位置
if(n<num[j])
j = j + (i + 1)
else if(n>num[j])
j = j - (i + 1)
else
{
isFound = 1
break //若找到相等数,标记已找到并退出循环
}
}
//输出结果
if(isFound)
printf("该数是数组中第%d个元素的值\n", j)
else
printf("查无此数!\n")
return 0
}