单调性与二分的关系:
有单调性一定可以二分,用二分不一定是单调性。(二者没有直接的关系)
二分的本质不是单调性而是边界点(找符合条件的最小的数或者最大的数)。
找到一个性质,使得我们可以把整个区间一分为二,一半满足,一半不满足,
二分就可以寻找这个性质的边界。
bool check(int x) {/* ... */} // 检查x是否满足某种性质
// 模板一
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid; // check()判断mid是否满足性质
else l = mid + 1;
}
return l;
}
// 模板二
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
第一个模板是尽量往左找目标,第二个模板是尽量往右找目标。
只要是往左找答案,就用第一个模板,mid不+1,r=mid,l+1;
只要是往右找答案,就用第二个模板,mid要+1,l=mid,r-1;
若题目明确要求最小值(最前面的值)还是求最大值(最后面的值),
就能判断是用模板1(求最小),还是用模板2(求最大)。
之后再根据模板1,或模板2,写出对应的判断条件
几乎所有整数二分问题都可用上述模板来解决
在区间内部,解决二分的边界问题时
(1)选择在哪个区间
(2)选择答案所在区间进行下一步的处理
(3)把整个区间长度缩小一半,然后选择一个答案所在区间都能保证区间里面一定会有答案
循环(1)(2)(3),当区间长度是 1 的时候,这个区间里面这个数就是答案。
二分的时候一定是有解,如果无解,是和题目有关的,与二分的模板是没有关系的,题目可能有无解的,但是二分一定是有解的。无解不是指二分无解,而是二分之后通过这个性质可以判断出来原题目无解,二分的时候,一定是可以边界二分出来的
定义的性质一定有边界,二分算法一定可以把这个边界找出来。若要求找到等于 x 的这个数,但是数组里面可能不包含 x。定义的这个性质是:从左往右看,第一个满足大于等于 x 的这个数,性质一定是有边界的,二分的这个数一定能够出来,要找的是大于等于 x 的数,如果找到的这个数大于 x,说明数组是无解的。
以下是一个简单实用例题
给定一个按照升序排列的长度为 n 的整数数组,以及 q 个查询。
对于每个查询,返回一个元素 k 的起始位置和终止位置(位置从 00 开始计数)。
如果数组中不存在该元素,则返回 -1 -1
。
输入格式
第一行包含整数 n 和 q,表示数组长度和询问个数。
第二行包含 n 个整数(均在 1∼100001∼10000 范围内),表示完整数组。
接下来 q 行,每行包含一个整数 k,表示一个询问元素。
输出格式
共 q 行,每行包含两个整数,表示所求元素的起始位置和终止位置。
如果数组中不存在该元素,则返回 -1 -1
。
数据范围
1≤n≤100000
1≤q≤10000
1≤k≤10000
输入样例:
6 3
1 2 2 3 3 4
3
4
5
输出样例:
3 4
5 5
-1 -1
#include<iostream>
using namespace std;
const int N=100010;
int n,m;
int q[N];
int main(){
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++) scanf("%d",&q[i]);
while (m--){
int x;
scanf("%d", &x);
int l=0, r=n-1;
while (l<r){
int mid=l+r>>1;
if (q[mid]>=x) r=mid;
else l=mid+1;
}
if (q[l]!=x) cout<<"-1 -1"<<endl;
else{
cout<<l<<' ';
int l=0, r=n-1;
while (l<r){
int mid=l+r+1>>1;
if (q[mid]<=x)l=mid;
else r=mid-1;
}
cout<<l<<endl;
}
}
return 0;
}