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