问题描述

　　二分查找又叫折半查找(Binary Search, Half-Interval Search)，在有序序列中可以用O(1)时间初始化，O(logN)的时间进行查找。
　　给定一个长为N的严格升序序列a(a[0], a[1] ... a[N-1])。有M个询问，每个询问有一个参数x，求x在a中的下标（从0开始），若不存在则为-1。

输入格式

　　输入共N+M+1行。
　　第一行两个整数N，M。
　　接下来N行，每行一个数，表示给定序列。
　　接下来

输出格式

　　输出共M行
　　每行一个数，表示所求下标。

样例输入

---

3 7
1
3
5
0
1
2
3
4
5
6

样例输出

---

-1
0
-1
1
-1
2
-1

数据规模和约定

　　共10组数据。

T	N	M
0	1	2*10^6
1	2	2*10^6
2	3	2*10^6
3	10	1.5*10^6
4	50	1.5*10^6
5	100	1.5*10^6
6	10^3	10^6
7	10^4	10^6
8	10^5	10^6
9	10^6	10^5

　　所有数均为非负整数且在int范围内。

基础代码（c++）

#include <iostream>
using namespace std; 
int main() {
    int N, M;
    cin >> N >> M;
    
    int a[N];
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }

    for (int i = 0; i < M; ++i) {
        int x;
        cin >> x;

        int left = 0, right = N - 1;
        int ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (a[mid] == x) {
                ans = mid;
                break;
            } else if (a[mid] < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        cout << ans << endl;
    }

    return 0;
}

 but*但是如果使用清橙网络自动评测系统

那么代码为

#include <cstdio>

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    
    int a[N];
    for (int i = 0; i < N; ++i) {
        scanf("%d", &a[i]);
    }

    for (int i = 0; i < M; ++i) {
        int x;
        scanf("%d", &x);

        int left = 0, right = N - 1;
        int ans = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (a[mid] == x) {
                ans = mid;
                break;
            } else if (a[mid] < x) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        printf("%d\n", ans);
    }

    return 0;
}

请C++选手使用scanf读入，cin会超时。

　　scanf用法： int soysauce; scanf("%d", &soysauce);