789. 数的范围

题目

给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。

如果数组中不存在该元素，则返回 -1 -1。

输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。

第二行包含 n 个整数（均在 1∼10000 范围内），表示完整数组。

接下来 q 行，每行包含一个整数 k，表示一个询问元素。

输出格式
共 q 行，每行包含两个整数，表示所求元素的起始位置和终止位置。

如果数组中不存在该元素，则返回 -1 -1。

数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例：
6 3
1 2 2 3 3 4
3
4
5
输出样例：
3 4
5 5
-1 -1

思路

二分，用两种二分模板，从左往右查找左边界，从右往左查找右边界
如果是从左往右查找缩小范围得话，即l=mid+1，则不需要注意死循环，在求mid时向下取整即可，即mid=l+(r-l>>1);防止数据溢出并向下取整
如果是从右往左缩小范围的话，即r=mid-1,则需要注意死循环，在求mid时，需要向上取整，即mid=l+(r-l+1>>1); 防止数据溢出并且向上取整
做题步骤

• 先找出查找的区间边界k左右两边的性质
• if(num[mid]满足左边的性质),看看mid是否包含在[l,k]区间内，如果边界答案k在mid的右半边，并且mid位置的元素不可能等于边界条件k，满足条件时更新查找的左边界为l=mid+1，与之对应的不满足性质时则更新右边界为r=mid,此时向下取整即可
• if(num[mid] 满足边界左边的性质)，看看mid是否包含在[l,k]区间内，如果边界答案k在mid的右半边，并且mid位置的元素有可能等于边界条件k，满足性质时则更新查找的左边界为l=mid，与之对应的不满性质时则更新右边界为r=mid-1，此时注意防止死循环需要向上取整(死循环：如果mid向下取整，mid=l+r>>1仍然等于l,当判断性质时更新的是左边界时执行l=mid，导致查找区间的左边界不会发生变化，没有更新右边界自然也不会右变化，陷入死循环)

代码

#include <iostream>

using namespace std;

const int N = 100010;
int num[N];

int main()
{
    
    int n, q;
    cin >> n >> q;
    for(int i = 0; i < n; i++)scanf("%d", &num[i]);
    
    while(q--){
    
        int k;
        cin >> k;
        int l = 0, r = n-1;
        
        
        //左边界逐渐从左往右移动
        //把区间分为[l,mid] [mid+1,r]
        while(l < r){
    
            int mid = l + (r-l>>1);//向下取整
            if(num[mid] < k) l = mid+1;
            else r = mid;
        }
        if(num[l] != k){
    
             printf("-1 -1\n");
             continue;
        }
        printf("%d ",l);     
        
        l = 0, r = n-1;
        //右边界逐渐从右往左移动
        //把区间分为[l, mid-1] [mid, r]
        while(l < r){
    
            int mid = l + (r-l+1 >> 1);//向上取整
            if(num[mid] <= k) l = mid;
            else r = mid-1;
        }
        printf("%d\n",l);
    }
    
    
    return 0;
}