数据结构之折半查找法——C语言实现

概念：

折半查找法又称为二分查找法，该方法要求带查找的表是顺序存储结构并且表中的关键字大小有序排列。

查找过程：

先确定待查记录所在的区间，然后逐渐通过待查找值与区间中间值进行比较进而调整区间大小，不断缩小范围，直到找到或者找不到为止。

具体方法：

将表中间值与待查找值进行比较，如果二者相等则查找成功；否则利用中间为止记录将表分成前后两个子表，如果待查找值大于区间中间值，则在后一个子表中继续查找；反之，则在前一个子表中查找。重复上述过程，直到找到目标值，则查找成功。否则，目标不存在，查找失败。

算法思想：

“分治法”，将一个大的区间，不断“折半”，在小区间内查找，分而治之。

实例：

题目描述：
任意输入十个整数，再输入一个整数，利用“折半查找法”验证该数字是否在该数列中。如果存在，则输出其序号；否则，输出不存在。
注释：不考虑大整数的情况
解析：首先，对于输入的十个整数，可能是无序的，所以要先用选择排序法进行排序。再利用折半查找法查找待查找数。

代码如下：

#include"stdio.h"
int main()
{
	void sort(int a[10],int m);//排序函数 
	void search(int a[10],int n);//查找函数 
	int a[10],n,i;
	printf("请输入10个整数：\n");
	for(i=0;i<10;i++)
	   scanf("%d",&a[i]);
	printf("请输入你想要查找的数字：\n");
	scanf("%d",&n);
	sort(a,10);
	search(a,n);
	return 0;
}
void sort(int a[10],int m)//选择排序法 
{
	int i,j,k,temp;
	for(i=0;i<m-1;i++)
	{
		k=i;
		for(j=i+1;j<m;j++)
		{
			if(a[j]<a[k])
			  k=j;
		}
		temp=a[i];a[i]=a[k];a[k]=temp;
	}
	printf("排序后：\n");
	for(i=0;i<m;i++)
	   printf("%d ",a[i]);
	printf("\n");
}
void search(int a[10],int n)
{
	int low=0,high=9,mid,flag;//low,high分别为区间的左端点和右端点，mid为区间中间，flag存放逻辑值 
	while(low<=high)
	{
		mid=(low+high)/2;//折半 
		if(n==a[mid])
		{
		  flag=1;//如果区间中间值等于待查找值，则查找成功，flag值为 1,为真 
		  break;//找到，则终止循环 
	    }
		else
		   if(n<a[mid])//待查找值小于中间值，则在前一半区间内继续查找 
		     high=mid-1;//调整右端点 
		   else if(n>a[mid])//待查找值大于中间值，则在后一半区间内继续查找 
		     low=mid+1;//调整左端点 
	}
	if(flag==1)//如果找到 
	  printf("found! 序号为：%d\n",mid+1);//mid为待查找值在数组中的下标，而mid+1才是人数数习惯中的下标 
	else
	  printf("NO found !\n");
}

调试结果：

总结：

折半查找法，又名二分查找法。仅适用于有序数组或数据，查找效率比顺序查找高。
即给定一个区间[low,high] ,low初始值为0，high初始值为数组长度减一。折半：mid=(low+high)/2,每次将待查找值n和区间中间值a[mid]进行比较
如果n<a[mid]，表明待查找值在区间中间左侧，则在前一半区间内继续查找，故使high=mid-1。
同理，如果n>a[mid],表明待查找值在区间中间右侧，则在后一半区间内继续查找，故使low=mid+1，
直到n=a[mid],表明查找成功，此时mid就是待查找值所在的数组下标，则在人为数数中是第mid+1个数字
但如果high<low则表明该数字不存在这串数列中，则查找失败。