2413: C语言习题 折半查找

题目描述

有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;
}

解析

暂无