【算法系列02】整数二分怎么玩？
——《洛克菲勒写给儿子的38封信》
大家好哇，这里是小编记录算法模板的宝地啦，其中也会包含小编平时学习的一些心得。现在，让我们一起进入算法的世界吧~ 本文思路来源于y总~
记得之前学C的时候接触过二分，不过那也是过去式了，现在写还真不一定写得出来。
二分可简单的分为整数二分和浮点数二分。如果说二分是否一定能得出结果，除开原题出问题，绝不会有第二种情况。二分是一定能有解的，当然前提得代码正确。
1.整数二分
整数二分更多的是容易出现边界问题，比如一个l到r的区域，在某个点分两边，左边满足其性质，而右边不满足。
这也说明二分实际上是一种边界问题，而不是单调性。有单调性的一定可以二分，没有单调性的部分问题也是可以二分的，当然具体问题具体分析。
说到边界问题，那么我们平时该如何判断呢？
从下图中可以看到，我们通过分析确定边界点：
1.如果是mid=(l+r+1)/2；再通过if(check(mid))检查，如果是true，则说明答案在区间[mid,r],将mid赋值给l；如果是false，则说明答案在区间[l,mid-1],将mid-1赋值给r。
2.如果是mid=(l+r)/2,通过if(check(mid))检查，如果是true，则说明答案在区间[l,mid]，将mid赋值给r；如果是false，则说明答案在区间[mid+1,r]，将mid+1赋值给l。
图片：来源于y总
做题时的大致步骤：
- 确定边界
- 补充check函数
- 选择模板
整数二分例题：数的范围
给定一个按照升序排列的长度为 n 的整数数组，以及 q 个查询。
对于每个查询，返回一个元素 k 的起始位置和终止位置（位置从 0 开始计数）。
如果数组中不存在该元素，则返回 -1 -1。
输入格式
第一行包含整数 n 和 q，表示数组长度和询问个数。
第二行包含 n 个整数（均在 1∼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 a[N];
void half(int x) {//函数模板 分两个部分
int r = 0, l = n - 1;
while (r < l) { //当区间[r,l]被划分为[r,mid]和[mid+1,l]
int mid = l + r >> 1;
if (a[mid] >= x) { //检查mid是否满足性质
l = mid;
} else {
r = mid + 1;
}
}
if (a[r] != x) {
cout << "-1 -1" << endl;
} else {
cout << r << " ";
r = 0, l = n - 1;
while (r < l) { //当区间[r,l]被划分为[r,mid-1]和[mid,l]
int mid = l + r + 1 >> 1;
if (r < l) {
if (a[mid] <= x) { //检查mid是否满足性质
r = mid;
} else {
l = mid - 1;
}
}
}
cout << r << endl;
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int x; //需要查询的数字
while (m--) { //共m个查询
scanf("%d", &x);
half(x);
}
return 0;
}平时也可多敲敲模板哦！
最后的话：刷题要找自己的不足，然后去专攻。
腾讯云开发者
