题目链接https://www.acwing.com/file_system/file/content/whole/index/content/4317/
当求左端点时,条件是a【mid】大于等于x,并把右端点缩小。
当求右端点时,条件是a【mid】小于等于x,并把左端点扩大。
1.确定一个区间,使得目标值一定在区间中
2.找一个性质满足:
(1)性质具有二段性
(2)答案是二段性的分界点
3.整数二分(处理红色右端点和绿色左端点)
//代码1:右端点
int l=0,r=n;
while(l < r){
int mid = (l+r+1) >> 1;
if(在红色段){
l = mid;
}
else r = mid - 1;
}
//代码2:左端点绿色
if是绿的,说明ans在【了,m】
int l=0,r=n;
while(l<r){
int mid = l+r >> 1;
if(是绿的){
r = mid;
}
else l = mid + 1;
}
例题:
在这道题中,因为开始已经求出左端点了,所以求右端点时l可以不动,只更新r为n-1
0402重写:
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
//要求左边界右边界
int n;
int a[100010];
int q;
int main()
{
scanf("%d%d",&n,&q);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
while(q--){
int x;
scanf("%d",&x);
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){
printf("%d ",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;
}
if(a[l] == x){
printf("%d\n",l);
}
}
else{
printf("-1 -1\n");
}
}
return 0;
}
代码:
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
int n,k;
int a[100010];
int main()
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
while(k--){
int q;
scanf("%d",&q);
//找区间左端点
int l=0,r=n-1;
while(l<r){
int mid = l+r >> 1;
if(a[mid] >= q)//中位数大于q,说明右端点在左半段
{
r = mid;
}
else l = mid + 1;
}
if(a[l] == q){
cout<<l<<" ";
//右端点
l = 0,r = n-1;
while(l < r){
int mid = (l + r + 1) >> 1;
if(a[mid] <= q){
l = mid;
}
else r = mid - 1;
}
if(a[l] == q){
cout<<l<<endl;
}
}
else {
cout<<"-1 -1"<<endl;
}
}
return 0;
}