C语言习题 折半查找
时间： 1ms 内存：128M
描述：
有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提示：
参考答案（内存最优[4900]）：
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n,t,l,h,k,j,i;
scanf("%d",&n);
int x[n];
for(i=0;i<n;i++)
scanf("%d",&x[i]);
scanf("%d",&t);
for(i=0;i<t;i++)
{
scanf("%d",&k);
l=0;
h=n-1;
while(l!=h)
{
if(x[(l+h)/2]<=k)
h=(l+h)/2;
else
l=(l+h)/2+1;
}
if(k==x[h])
printf("%d\n",h+1);
else
printf("0\n");
}
return 0;
}
参考答案（时间最优[181]）：
#include<stdio.h>
int a[1000001];
int main()
{
int i,j,n,T,m,result=0;
int searchfor(int a[],int n,int m);
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
scanf("%d",&T);
while(T--)
{
scanf("%d",&m);
//printf("1\n");
result=searchfor(a,n,m);
printf("%d\n",result);
//printf("1\n");
}
return 0;
}
int searchfor(int a[],int n,int m)
{
int low,height,i,j,mid;
low=0,height=n-1;
int mina=99999999;
int flag=0;
while(low<=height)
{
mid=(height+low)/2;
if(a[mid]==m){
if(mina>mid)
{
mina=mid;
}
height=mid-1;
flag=1;
}
if(a[mid]<m)
{
height=mid-1;
}
if(a[mid]>m)
{
low=mid+1;
}
}
if(flag==0)
mina=0;
else
mina+=1;
return mina;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。