C++ 代码

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100010;

int A[N];

// predicate函数
bool check(int x, int k) {
    return A[x] >= k;
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; ++i) 
        scanf("%d", &A[i]);

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

        // idea：转化成查找 F F F...F T T...T 的边界

        // 1. 查找第一个>=k的位置
        // F F F...F [T] T...T
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (check(mid, k))
                r = mid;
            else
                l = mid + 1;
        }
        // 循环结束，l等于r，若找到的第一个>=k的数不是k，则有两种情况：
        // 1. 根本没有数>=k，check(l, k)返回的是false，所有数都<k；
        // 2. check(l, k)返回true，但A[l] > k。
        // 无论是哪一种情况，都告诉我们k不在数组中，所以返回"-1 -1"。
        if (A[l] != k) {
            printf("-1 -1\n");
            continue;
        }
        int start = l;
        // 2. 从==k的位置出发，查找最后一个<=k的位置，就可以得到最后一个==k的位置。
        // 注意到<=k为true等价于>k为false（已经小于等于k了就不可能大于k）等价于>=k+1为false，
        // 所以要找的是最后一个>=k+1为false的位置
        // F F F...[F] T...T
        r = n - 1;  // note: 此时A[l]==k
        while (l < r) {
            int mid = l + (r - l + 1) / 2;
            if (check(mid, k + 1))
                r = mid - 1;
            else
                l = mid;
        }
        // 循环结束，l等于r，此时check(l, k + 1)一定为false，
        // 这是因为循环开始前我们是在==k的位置，即A[l]==k，所以check(l, k + 1)为false，也就是说false一定是存在的，可以排除check(x, k + 1)全部为true的情形
        // 因此l就是要找的最后一个>=k+1为false的位置
        int end = l;
        printf("%d %d\n", start, end);
    }
    return 0;
}