点击查看代码
#include<iostream>
using namespace std;
const int N = 100010;
int n, m;
int q[N];
int main(){
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> q[i];
while(m--){
int x;
cin >> 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;
}
}//模板r = mid
if(q[l] != x){
cout << "-1 -1" << endl; //数组中不存在元素x
}
else{
cout << l << ' '; //元素x的起始位置
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;
}
}//模板l = mid
cout << l << endl; //元素x的终止位置
}
}
return 0;
}
/*
整数二分:
本质并不是单调性
但与单调性的关系是:
如果有单调性则一定可以二分
但可以二分的题目不一定非得有单调性
本质是边界
找到一个性质
整个区间一分为二
左半边不满足性质 右半边满足性质
可以找到分界处的两个边界点
对应两个模板
第一种情况:想二分左半边的边界点时
mid = (L+R+1) / 2 //加1是为了防止死循环
if(check(mid))
情况 答案新区间 更新
true [mid,R] L=mid
false [L,mid-1] R=mid-1
模板:
//区间[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 = (L+R) / 2
if(check(mid))
情况 答案新区间 更新
true [L,mid] R=mid
false [mid+1,R] L=mid+1
模板:
//区间[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;
else l = mid+1;
}
return l;
}
二分的模板是一定要保证有解的
原本的题是可以无解的 二分不用考虑无解
方法:
先写一个mid
随便先想一个check函数(想清楚性质)
根据check函数的值想一下答案是怎么去划分的
选择答案所在的区间
true 时答案在哪个边界里面
false时答案在哪个边界里面
更新时是L=mid还是R=mid
确定求mid处是否需要补上+1
*/
- 性质划分,确定答案所在区间,确定如何更新区间边界
- 两种情况:L=mid时mid=(l+r+1)/2; R=mid时mid=(l+r)/2
- 模板记忆
原文地址:http://www.cnblogs.com/starryWJ/p/16876570.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性