关于二分法查找的一点问题,能有高手帮我看一下吗?谢谢~
这里有一道题目: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),就一直在运行没有输出,求指点迷津,万分感谢




