题目

• 给定一个按照升序排列的长度为$ n$ 的整数数组，以及$ q $个查询。
• 对于每个查询，返回一个元素$ k $的起始位置和终止位置（位置从 $0$ 开始计数）。
• 如果数组中不存在该元素，则返回 $-1 -1$。

本文题目：数的范围

代码

代码详解整数二分模板

• 寻找左右边界时，要注意$mid$的取值，由于$ mid = l + r >> 1 $ 是默认向下取整，也就是说等价于 $ mid = l$;
• 我们在更新：$l = mid;$ 时，要把 $mid = l + r + 1 >> 1;$ 防止死循环；否则就成了 $l = l;$ 即陷入死循环

#include<iostream>
using namespace std;

int main() {
    int len, m, x;
    cin >> len >> m;
    int nums[len];
    for(int i = 0; i < len; i++ ) cin>> nums[i];
    while(m--) {
        cin >> x;
        int l = 0, r = len - 1;
        // 查找左边界
        while(l < r) {
            int mid = l + r >> 1;
            if(nums[mid] >= x) r = mid;
            else l = mid + 1;
        }
        // 此时已经找到了左边界（比 x 大的第一个数）
        if(nums[l] != x)    cout<<"-1 -1"<<endl;  // 若不等于 x，即不存在
        else{
            cout << l << " ";
            
            l = 0; r = len - 1;
                        // 查找右边界
            while(l < r) {
                int mid = l + r + 1 >> 1;
                if(nums[mid] <= x)  l = mid;
                else r = mid - 1;
            }
            cout<< l <<endl;
        }
    }
    return 0;
}

• 要理解记忆这两个模板，注意查找右边界时，不断地更新 l ,尤其要注意防止死循环