789.数的范围

tip

原题链接：https://www.acwing.com/problem/content/791/

思路

因为题目已经给出数组升序，所以直接使用二分，只要找到对应的左边界和有边界即可找到对应数的范围。所以使用一次二分找到左边界，再使用一次找到右边界。

• 要注意 mid 是否需要加 1，以及 l 和 r 的边界。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, q;
int a[N];

int main() {
    cin >> n >> q;
    
    for (int i = 0; i < n; i++) cin >> a[i];
    
    while (q --) {
        int k;
        cin >> k;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (a[mid] >= k) r = mid;
            else l = mid + 1;
        }
        if (a[l] != k) cout << "-1 -1" << endl;
        else {
            cout << l << " ";
            
            int l = 0, r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (a[mid] <= k) l = mid;
                else r = mid - 1;
            }
            cout << l << endl;
        }
    }
    
    return 0;
}