关于二分法查找的一点问题,能有高手帮我看一下吗?谢谢~
这里有一道题目:Description
编写一个函数实现数组的折半查找(即二分查找)。
该函数的原型为:
int binary_search(int d[], int s, int e, int q);
注意:不要修改函数的名称、返回值、参数类型和名称。
其中d是数组,s是起始下标,e是终止下标,q是要查找的数据。
请使用折半查找(即二分查找)来求解,否则会得到 Time Limit Exceeded 的结果噢。
由于本题的输入数据达到万级别,请大家在主函数外定义一个大小为2万的int数组(全局变量)来进行操作。
int data[20000];
int main()
{
return 0;
}
Input
首先是一个整数n(n不大于2万),
接下来有n个整数,所有的整数是递增排列(无重复数字)。
然后是一个整数m(m不大于10万),接下来有m组查询,
每组查询包含三个数据:s e q,求数组[s, e)中 数字q 在数组所处位置中的下标。
注意,[s, e)是左闭右开区间。Output对于每一组s e q,输出数组[s, e)中q在位置的下标。如果数字q不在[s, e)中,输出-1。Sample Input10
0 1 2 3 4 5 6 7 8 9
3
0 10 1
0 4 4
6 8 7
Sample Output
1
-1
7
然后这是我尝试写的代码,编译无误:
程序代码:
#include<stdio.h> int binary_search(int d[],int s,int e,int q); int data[20000]; int main(){ int n,m,j,l,t,h,x; scanf("%d",&n); for(j=0;j<n;j++){ scanf("%d",&data[j]); } scanf("%d",&m); for(t=0;t<m;t++){ scanf("%d %d %d",&l,&h,&x); printf("%d\n",binary_search(data,l,h,x)); } return 0; } int binary_search(int d[],int s,int e,int q){ int mid,i=0; if(q<s&&q>e) return -1; else while(s<=e&&i==0){ mid=(int)(s+e)/2; if(q==d[mid]) i=mid; else if(q<d[mid]) e=mid+1; else s=mid-1; } return i; }
结果运行上出了一点问题,当输入数据是在{0 1 2 3 4 5 6 7 8 9}中查找[0,4)中4的下标时(本来应该输出-1),就一直在运行没有输出,求指点迷津,万分感谢