免费软件下载网站app网络营销 企业网站

题目链接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;
}