ACM-递归递推练习P-二分查找

（欢迎阅读我的博客，如发现错误或有建议请评论留言，谢谢。）

题目要求：

Description

给出含有n个数的升序序列，保证序列中的数两两不相等，这n个数编号从1 到n。

然后给出q次询问，每次询问给出一个数x，若x存在于此序列中，则输出其编号，否则输出-1。

Input

单组输入。首先输入一个整数n(1 <= n && n <= 3000000)，接下的一行包含n个数。

再接下来的一行包含一个正整数q(1 <= q && q <= 10000),表示有q次询问。

再接下来的q行，每行包含一个正整数x。

Output

对于每次询问，输出一个整数代表答案。

Sample Input

5
1 3 5 7 9
3
1
5
8

Sample Output

1
3
-1

题目思路：

一看题目思路就很明确了用二分查找，题目限制600MS，用for直接找肯定超时了。

细节处理：

在写程序的时候我遇到一个问题，一开始用C++写的程序用了二分也是超时，后来在贴吧上看到了有个人也是用C++写完后超时，但是改为C以后就A了，搜索了一下发现C与C++之间的效率是有略微差别的。

下面这个网址中就有对二者效率的说明http://bbs.****.net/topics/390326288?locationNum=6&fps=1

代码如下：

#include<stdio.h>
int main()
{
    int n,i,q,s,a[3000000],k,m,x;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    scanf("%d",&q);
    while(q--)
    { k=0;
        scanf("%d",&x);
        m=n-1;
        int w=1;
        while(k<=m)
        {
           s=(k+m)/2;
           if(x==a[s])
           {
               w=0;break;
           }
           else if(x<a[s])
           {
               m=s-1;
           }
           else k=s+1;
        }
        if(w==0)
            printf("%d\n",s+1);
        else printf("-1\n");
        }
}