整数二分 - AcWing 789. 数的范围（C++）- 简单

题目链接：https://www.acwing.com/problem/content/description/791/
题目如下：

#include <iostream>
using namespace std;
const int N=100010;
int n,q;
int a[N];
//思路：对左右边界分别进行二分，分别找到左右的值不等于x的那个边界
//注: 当满足条件时为l=mid,则初始mid需+1;若满足条件为r=mid,则初始mid不需+1,且最终找到的目标值都在l中
int main(){
    cin>>n>>q;
    for(int i=0;i<n;++i) cin>>a[i];
    
    while(q--){
        int x;
        cin>>x;
        //找左边界，二分模板一：区间为[l,mid]和[mid+1,r]        
        int l=0,r=n-1;
        while(l<r){
            int mid=l+r>>1;
            if(a[mid]>=x) r=mid;
            else l=mid+1;
        }
        
        if(a[l]!=x) cout<<"-1 -1"<<endl;
        else {
            cout<<l<<' ';
            //找右边界，二分模板二：区间为[l,mid-1]和[mid,r]    
            int l=0,r=n-1;
            while(l<r){
                int mid=l+r+1>>1;
                if(a[mid]<=x) l=mid;
                else r=mid-1;
            }
            
            cout<<l<<endl;
        }
    }
    
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39