WHCSRL 技术网

整数二分 - 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
推荐阅读