题意

给定一个严格单调的数列，询问若干个数分别需要在数列中二分几次才能找到。如果能找到，输出二分的次数；如果不能找到，输出 NONE。二分查找参考程序如下：

（数列单调递增时）

1
2
3
4
5
6
7
8
l = 1, r = n, cnt = 0;
while (l <= r) {
    mid = (l + r) / 2;
    cnt++;
    if (a[mid] == key) break;
    if (a[mid] > key) r = mid - 1;
    else l = mid + 1;
}

（数列单调递减时）

1
2
3
4
5
6
7
8
l = 1, r = n, cnt = 0;
while (l <= r) {
    mid = (l + r) / 2;
    cnt++;
    if (a[mid] == key) break;
    if (a[mid] > key) l = mid + 1;
    else r = mid - 1;
}

上述程序中结束时 cntcnt 的值即为二分次数。

输入格式

第一行两个整数 n*,*m 分别表示数列长度和询问次数。

第二行 n 个整数，第 i 个表示 ai。

接下来 m 行，每行一个整数 x 表示要求询问的数。

输出格式

共 m 行，如果能找到，输出二分的次数；如果不能找到，输出 NONE。

思路

一道板子题一直超时，参考了别人的代码才知道了应该设置一个新的数组存储输入数据。具体做法是：对重复出现的输入数据只进行一次（对第一次）计算并记录，则后续出现重复数据时不用再次计算。这样做可以在查询次数非常大时省去大量时间。

（反思：以后碰到查询次数远大于数据范围并且计算结果可复用的题目要想到这个小操作。）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>

using namespace std;

const int N = 1e6 + 5;

int n, m, k, l, r, mid, cnt;
int q[N], arr[N];
bool is;

inline void bs(int k) {
    if (arr[k]) return;

    l = 1, r = n, cnt = 0;
    if (is) {
        while (l <= r) {
            mid = (l + r) >> 1;
            ++ cnt;
            if (q[mid] == k) {
                arr[q[mid]] = cnt;
                return;
            }
            if (q[mid] > k) r = mid - 1;
            else l = mid + 1;
        }
    } else {
        while (l <= r) {
            mid = (l + r) >> 1;
            ++ cnt;
            if (q[mid] == k) {
                arr[q[mid]] = cnt;
                return;
            }
            if (q[mid] > k) l = mid + 1;
            else r = mid - 1;
        }
    }
}

int main() {
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%d", &q[i]);
    is = (q[1] <= q[n]);

    while (m -- ) {
        scanf("%d", &k);
        bs(k);
        if (arr[k]) printf("%d\n", arr[k]);
        else printf("NONE\n");
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
}