【模板】常见整数二分

发布于 25 天前  1 次阅读


#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 998244353;
int n, q, a[N];

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    while (q--) {
        int k;
        scanf("%d", &k);
        int l = 1, r = n, mid;
        while (l < r) {
            mid = l + r >> 1;
            if (a[mid] >= k) r = mid;
            else l = mid + 1;
        }
        if (a[l] != k) printf("-1 -1\n");
        else {
            printf("%d ", l - 1);
            l = 1, r = n;
            while (l < r) {
                mid = l + r + 1 >> 1;
                if (a[mid] <= k) l = mid;
                else r = mid - 1;
            }
            printf("%d\n", l - 1);
        }
    }
    return 0;
}