题目描述
有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
参考代码
#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("1n");
result=searchfor (a,n,m);
printf("%dn",result);
//printf("1n");
}
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;
}
解析
暂无