二分模板

例题：AcWing 789. 数的范围

原题：

使用二分查找数值 \(x\) 的范围 \([l,r)\)。

注意：采用左闭右开的方式，这个时候返回右端点时会比最大编号多一，输出时要 \(-1\)。而求最小编号时不受影响。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
using PII = pair<int, int>;

const int N = 100010;

int a[N];
int n, m;

PII query(int x) {
    int l = 0, r = n, res1 = 0;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    res1 = l;
    if (a[l] != x) return make_pair(-1, -1);
    
    l = 0, r = n;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] <= x) l = mid + 1;
        else r = mid;
    }
    
    return make_pair(res1, l - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> a[i];
    
    while (m--) {
        int x;
        cin >> x;
        PII res = query(x);
        cout << res.first << ' ' << res.second << '\n';
    }
    return 0;
}