（哭晕！！！让人心态爆炸的查找！！！！）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

提示

注意：数组空间为1000000和100000

#include<stdio.h>///用C能杀%25的时间！！！
int n,i,j,k,index,array[1000001],key;
int binary_search(int array[],int n,int key)
{
    int index=-1,left=-1,right=n-1,mid;
    while(left<=right)
    {
        mid=left+(right-left)/2;
        if(key==array[mid])
        {///第一个大坑！！！
            for(i=left; i<=mid; i++)
            {///如果找到还得确定他是第一个！！！
             ///从开始到该元素所在的mid找该元素
             ///这之间如果能找到就是第一个！！！
                if(array[i]==key)
                {
                    index=i;
                    break;
                }
            }
            break;
        }
        if(key==array[0])
            return 1;
        ///卢老师加了一个条件，我把它找了出来，就是进行一个特判！！！
        ///这个条件加的太好了！！！如果不加会发现‘1222222222’查找1会输出0？！
        ///如果第一个数就是，返回1就好了（滑稽）
        else if(key<array[mid])
            left=mid+1;
        else
            right=mid-1;
    }
    return index+1;
}
int main()
{
    scanf("%d",&n);
    for(i=0; i<n; i++)
    scanf("%d",&array[i]);
    ///一直用C++，忘了C怎么写了，天哪！！！WA了无数次也没发现忘了加&！！！！！
    ///哭辽。。。。
    scanf("%d",&k);
    while(k--)
    {
        scanf("%d",&key);
        index=binary_search(array,n,key);
        if(index>=0)
        printf("%d\n",index);
    }
}
///对比了一下，发现快读时间好像没有差别。。。。。。
inline char gc()
{
    static char buff[100000000],*S=buff,*T=buff;
    return S==T&&(T=(S=buff)+fread(buff,1,100000000,stdin),S==T)?EOF:*S++;
}