题目AcWing 789. 数的范围
整数二分查找
寻找前半部分终点
mid=l+r+1>>1;
if(chaek( a[mid]在前半部分 ))l=mid;
else r=mid-1;
寻找后半部分起点
mid=l+r>>1;
if(chaek( a[mid]在后半部分 ))r=mid;
else l=mid+1;
#include <iostream>
const int N = 100000;
int a[N];
using namespace std;
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i = 0;i<n;i++)scanf("%d",a+i);
while(m--){
int x;
scanf("%d",&x);
int p,q,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)printf("-1 -1\n");
else{
p = l;
l=0,r=n-1;
while(l<r){//前半部分终点
int mid =l+r+1>>1;
if(a[mid]<=x) l = mid;
else r = mid-1;
}
q = l;
printf("%d %d\n",p,q);
}
}
}