折半查找 解题报告

折半查找 解题报告

折半查找是查找方法中的一种，常用的查找方法还有遍历查找。 折半查找运用了二分的思想，也可称为二分查找。其思想是在有序数组a（ 必须是有序的，从小到大或从大到小都可以）查找指定元素k，则将数组的中间元素啊a[mid]与k进行比较，如果a[mid]与k相等则已查找到；如果a[mid]与k不等，则需根据a[mid]与k的大小关系，在相应的数组前半段或是后半段中进行查找，不断缩小查找范围(第i次的查找范围是第i-1次的一半)，此时需要 递归调用二分查找函数。 二分查找函数可表示为：

int binaryfind(int a[],int k,int low,int high);

其中，a[]代表待查找的数组，k代表查找元素，low和high限定了在数组a中的查找范围，从low-1位置开始查找到high-1位置（因为数组下标从零开始），并且mid=(low+high)。 注意 由于数组a中可能会存在相等的元素，若要求输出k在数组a中第一次出现的位置，可以在第一次查找到与元素k相等的元素位置后，仍然调用二分查找函数，直到查找的范围是1，则此时便找到了元素k在数组a中第一次出现的位置。 例题

题目描述 有n个数（n<=1000000）,这n个数已按从大到小顺序存放在一个数组中，然后有T次查询，每次输入一个数，要求用折半查找法找出该数在数组中第一次出现的位置。如果不在数组中输出0。

输入 第一行数组元素的个数n 第二行n个数组元素的值 第三行输入查询次数T (T<=100000) 往下有T行，每行输入一个需要查询的数字 输出 查找的值在数组中的位置

样例输入 10 10 9 8 7 6 5 4 3 2 1 2 9 5 样例输出 2 6

这道题目是典型的折半查找题目，输出查找元素在数组中第一次出现的位置，编写折半查找函数，再进行递归调用即可。 细节注意 1、由于要求n<1000000,直接定义数组无法申请如此大的数组空间，因而要用到malloc函数。（当题目中要求的数组空间比较大时，一定要第一时间想到这样申请空间） 2、在折半查找函数中，如何突显出查找的范围变为1了呢？其实当查找的范围为1时，满足的条件是low=high，此时如果a[mid]==k,代表查找到了k在数组中第一次出现的位置，否则数组中不存在k。（一定要注意这个条件，条件写的不正确的话有的数会查找不到） 代码实现（可能会有瑕疵、冗余,通过了OJ测试）

#include<stdio.h>
#include<stdlib.h>
int binaryfind(int a[],int num,int low,int high) //二分查找函数的定义
{
	int mid;
	mid=(low+high)/2;
	while(low<high)
	{
		if(a[mid]==num) //即便查找到但不一定是第一次出现的位置，继续调用二分查找函数
 		{
			return binaryfind(a,num,low,mid);
		}
		else if(a[mid]>num)
		{
			return binaryfind(a,num,mid+1,high);
		}
		else if(a[mid]<num)
		{
			return binaryfind(a,num,low,mid-1);
		}
	}
	if(low==high && a[mid]==num)   //这个条件是重点，表明查找范围是1，并且a[mid]==num
	{
		return low+1;
	}
	return 0;   //查找不到返回0
}
int main()
{
	int i,m,n;
	int *a=(int *)malloc(1000001*sizeof(int));
	scanf("%d",&m);
	for(i=0;i<m;i++)
	{
		scanf("%d",&a[i]);
	}
	scanf("%d",&n);
	int num;
	for(i=0;i<n;i++)
	{
		scanf("%d",&num);
		printf("%d\n",binaryfind(a,num,0,m-1));
	}
	return 0;
}

（必须熟练了解算法原理，能够熟练写出代码，并注重其中的细节，并不是为了追求提交正确就可以，而是有所思、有所获）