手撕算法——二分
二分算法的核心思想是利用有序性不断缩小查找范围，可以在暴力遍历查找目标元素的过程中，快速定位目标元素的位置，从而优化时间复杂度。
这是经典的以缩小搜索范围来降低时间开销的做法，并不需要额外的大量空间。
学完二分算法之后，大家会发现，二分算法与顺序查找是两种效率差异较大的查找方式，顺序查找在无序数据中适用，而二分算法更适合处理有序数据。
【算法原理】
当我们的解具有⼆段性时，就可以使⽤⼆分算法找出答案：
- 根据待查找区间的中点位置，分析答案会出现在哪⼀侧；
- 接下来舍弃⼀半的待查找区间，转⽽在有答案的区间内继续使⽤⼆分算法查找结果。
【模板】
⼆分的模板在⽹上⾄少能搜出来三个以上。但是，我们仅需掌握⼀个，并且⼀直使⽤下去即可。
//
⼆分查找区间左端点
int l = 1, r = n;
while(l < r)
{
int mid = (l + r) / 2;
if(check(mid)) r = mid;
else l = mid + 1;
}
//
⼆分结束之后可能需要判断是否存在结
果 //
⼆分查找区间右端点
int l = 1, r = n;
while(l < r)
{
int mid = (l + r + 1) / 2;
if(check(mid)) l = mid;
else r = mid - 1;
}
//
⼆分结束之后可能需要判断是否存在结
果为了防⽌溢出，求中点时可以下⾯的⽅式：
mid = l + (r - l) / 2【时间复杂度】
每次⼆分都会去掉⼀半的查找区域，因此时间复杂度为 logN 。
【模板记忆⽅式】
- 不⽤死记硬背，算法原理搞清楚之后，在分析题⽬的时候⾃然⽽然就知道要怎么写⼆分的代码；
- 仅需记住⼀点，if /else 中出现 −1 的时候，求 mid 就 +1 就够了。
【⼆分问题解决流程】
- 先画图分析，确定使⽤左端点模板还是右端点模板，还是两者配合⼀起使⽤；
- ⼆分出结果之后，不要忘记判断结果是否存在，⼆分问题细节众多，⼀定要分析全⾯。
【STL中的⼆分查找】
一、二分模板
题⽬来源：⼒扣
题⽬链接：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
难度系数：★★
1. 题目描述
2. 算法原理
注意：left + right 范围在10^9,相加可能会达到10^10超出范围，以下为解决方法
- 1. 公式转换
- 2. 所有变量换成 long long
3. 参考代码
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n = nums.size();
//处理边界情况
if(n == 0) return {-1, -1};
//1. 求起始位置
int left = 0,right = n - 1;
while(left < right){
int mid = (left + right) / 2;
if(nums[mid] >= target) right = mid;
else left = mid + 1;
}
// left 或者 right 所指的位置就有可能是最终的结果
if(nums[left] != target) return {-1, -1};
int retleft = left;//记录一下起始位置
//2. 求终止位置
left = 0, right = n - 1;
while(left < right){
int mid = (left + right + 1) / 2;
if(nums[mid] <= target) left = mid;
else right = mid - 1;
}
return {retleft,left};
}
};二、二分查找
1. ⽜可乐和魔法封印
题⽬来源：⽜客⽹
题⽬链接：牛可乐和魔法封印
难度系数：★★
（1）题目描述
（2）算法原理
⼆分查找算法模版题，直接上⼿模版即可。
但是需要注意，有可能并没有这个区间，需要在⼆分结束之后判断⼀下。
（3）参考代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
int binary_search(int x, int y)
{
// 大于等于 x 的最小元素
int left = 1, right = n;
while(left < right)
{
int mid = (left + right) / 2;
if(a[mid] >= x) right = mid;
else left = mid + 1;
}
if(a[left] < x) return 0;
int tmp = left;
// 小于等于 y 的最大元素
left = 1, right = n;
while(left < right)
{
int mid = (left + right + 1) / 2;
if(a[mid] <= y) left = mid;
else right = mid - 1;
}
if(a[left] > y) return 0;
return left - tmp + 1;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
int Q; cin >> Q;
while(Q--)
{
int x, y; cin >> x >> y;
cout << binary_search(x, y) << endl;
}
return 0;
}2. A-B 数对
题⽬来源：洛⾕
题⽬链接：P1102 A-B 数对 - 洛谷
难度系数：★
（1） 题目描述
（2）算法原理
由于顺序不影响最终结果，所以可以先把整个数组排序。
由 A − B = C 得： B = A − C ，由于 C 是已知的数，我们可以从前往后枚举所有的 A ，然后去前⾯找有多少个符合要求的 B ，正好可以⽤⼆分快速查找出区间的⻓度。
【STL的使⽤】
1. lower_bound：传⼊要查询区间的左右迭代器（注意是左闭右开的区间，如果是数组就是左右指 针）以及要查询的值 k，然后返回该数组中 ≥k 的第⼀个位置；
2. upper_bound：传⼊要查询区间的左右迭代器（注意是左闭右开的区间，如果是数组就是左右指 针）以及要查询的值 k ，然后返回该数组中 ≥k 的第⼀个位置；
⽐如：a =[10,20,20,20,30,40]，设下标从 1 开始计数，在整个数组中查询 20 ：
- lower_bound(a + 1, a + 1 + 6, 20) ，返回 a + 2 位置的指针；
- upper_bound(a + 1, a + 1 + 6, 20) ，返回 a + 5 位置的指针；
- 然后两个指针相减，就是包含 20 这个数区间的⻓度。
【注意】
- 虽然了；ST L ⽤起来很爽，但是不要依赖它。因为后续学习「⼆分答案」的时候，ST L 就⽆法使⽤
- 同时ST L 的使⽤范围很「局限」，查询「有序序列」的时候才有⽤，数组⽆序的时候就⽆法使⽤。但是我们的⼆分模板也能在「数组⽆序」的时候使⽤，只要有「⼆段性」即可。
（3）参考代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL n, c;
LL a[N];
int main()
{
cin >> n >> c;
for(int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
LL ret = 0;
for(int i = 2; i <= n; i++)
{
// a[i]
LL b = a[i] - c;
ret += upper_bound(a + 1, a + i, b) - lower_bound(a + 1, a + i, b);
}
cout << ret << endl;
return 0;
}3. 烦恼的⾼考志愿
题⽬来源：洛⾕
题⽬链接：P1678 烦恼的高考志愿 - 洛谷
难度系数：★★
（1）题目描述
（2）算法原理
解法一：利用 set 解决问题
解法二：排序 + 二分
先把学校的录取分数「排序」，然后针对每⼀个学⽣的成绩 b ，在「录取分数」中⼆分出 ≥ b 「第⼀个」位置 pos ，那么差值最⼩的结果要么在 pos 位置，要么在 pos − 1 位置。取 abs(a[pos] − b) 与 abs(a[pos − 1] − b) 两者的「最⼩值」即可。
细节问题：
- 如果所有元素都⼤于 b 的时候，pos − 1 会在 0 下标的位置，有可能结果出错；
- 如果所有元素都⼩于 b 的时候，pos 会在 n 的位置，此时结果倒不会出错，但是我们要想到这个细节问题，这道题不出错不代表下⼀道题不出错。加上两个左右护法，结果就不会出错了。
（3）参考代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m;
LL a[N];
int find(LL x)
{
int left = 1, right = m;
while(left < right)
{
int mid = (left + right) / 2;
if(a[mid] >= x) right = mid;
else left = mid + 1;
}
return left;
}
int main()
{
cin >> m >> n;
for(int i = 1; i <= m; i++) cin >> a[i];
sort(a + 1, a + 1 + m);
// 加上左右护法
a[0] = -1e7 + 10;
LL ret = 0;
for(int i = 1; i <= n; i++)
{
LL b; cin >> b;
int pos = find(b);
ret += min(abs(a[pos] - b), abs(a[pos - 1] - b));
}
cout << ret << endl;
return 0;
}三、⼆分答案
准确来说，应该叫做「⼆分答案+判断」。
⼆分答案可以处理⼤部分「最⼤值最⼩」以及「最⼩值最⼤」的问题。如果「解空间」在从⼩到⼤的 「变化」过程中，「判断」答案的结果出现「⼆段性」，此时我们就可以「⼆分」这个「解空间」， 通过「判断」，找出最优解。
刚接触的时候，可能觉得这个「算法原理」很抽象。没关系， 3 道题的练习过后，你会发现这个「⼆ 分答案」的原理其实很容易理解，重点是如何去「判断」答案的可⾏性。
1. ⽊材加⼯
题⽬来源：洛⾕
题⽬链接：P2440 木材加工 - 洛谷
难度系数：★★
（1）题目描述
（2）算法原理
学习「⼆分答案」这个算法，基本上都会把这道⽐较简单的题当成例题~
设要切成的⻓度为 x ，能切成的段数为 c 。根据题意，我们可以发现如下性质，：
- 当 x 增⼤的时候，c 在减⼩。也就是最终要切成的⻓度越⼤，能切的段数越少；
- 当 x 减⼩的时候，c 在增⼤。也就是最终要切成的⻓度越⼩，能切的段数越多。
那么在整个「解空间」⾥⾯，设最终的结果是 ret ，于是有：
- 当 x ≤ ret 时， c ≥ k 。也就是「要切的⻓度」⼩于等于「最优⻓度」的时候，最终切出来的段数「⼤于等于」 k ；
- 当 x > ret 时， c < k 。也就是「要切的⻓度」⼤于「最优⻓度」的时候，最终切出来的段数「⼩于」 k ；
在解空间中，根据 ret 的位置，可以将解集分成两部分，具有「⼆段性」，那么我们就可以「⼆分答 案」。
当我们每次⼆分⼀个切成的⻓度 x 的时候，如何算出能切的段数 c ？
- 很简单，遍历整个数组，针对每⼀根⽊头，能切成的段数就是 a[i] / x 。
（3）参考代码
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL n, k;
LL a[N];
// 当切割长度为 x 的时候，最多能切出来多少段
LL calc(LL x)
{
LL cnt = 0;
for(int i = 1; i <= n; i++)
{
cnt += a[i] / x;
}
return cnt;
}
int main()
{
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i];
LL left = 0, right = 1e8;
while(left < right)
{
LL mid = (left + right + 1) / 2;
if(calc(mid) >= k) left = mid;
else right = mid - 1;
}
cout << left << endl;
return 0;
}2. 砍树
题⽬来源：洛⾕
题⽬链接：P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷
难度系数：★★
（1）题目描述
（2）算法原理
设伐⽊机的⾼度为 H ，能得到的⽊材为 C 。根据题意，我们可以发现如下性质，：
- 当 H 增⼤的时候，C 在减⼩；
- 当 H 减⼩的时候，C 在增⼤。
那么在整个「解空间」⾥⾯，设最终的结果是 ret ，于是有：
- 当 H ≤ ret 时， C ≥ M 。也就是「伐⽊机的⾼度」⼤于等于「最优⾼度」时，能得到的⽊材「⼩于等于」 M ；
- 当 H > ret 时， C < M 。也就是「伐⽊机的⾼度」⼩于「最优⾼度」时，能得到的⽊材「⼤于」 M 。
在解空间中，根据的位置，可以将解集分成两部分，具有「⼆段性」，那么我们就可以「⼆分答 案」。
当我们每次⼆分⼀个伐⽊机的⾼度 的时候，如何算出得到的⽊材 C
- 很简单，遍历整个数组，针对每⼀根⽊头，能切成的⽊材就是 a[i] − H 。
（3）参考代码
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
LL n, m;
LL a[N];
// 当伐木机的高度为 x 时，所能获得的木材
LL calc(LL x)
{
LL ret = 0;
for(int i = 1; i <= n; i++)
{
if(a[i] > x) ret += a[i] - x;
}
return ret;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
LL left = 1, right = 2e9;
while(left < right)
{
LL mid = (left + right + 1) / 2;
if(calc(mid) >= m) left = mid;
else right = mid - 1;
}
cout << left << endl;
return 0;
}3. 跳⽯头
题⽬来源：洛⾕
题⽬链接：P2678 [NOIP 2015 提高组] 跳石头 - 洛谷
难度系数：★★
（1）题目描述
（2）算法原理
设每次跳的最短距离是 x ，移⾛的⽯头块数为 c
根据题意，我们可以发现如下性质：
- 当 x 增⼤的时候， c 也在增⼤；
- 当 x 减⼩的时候， c 也在减⼩。
那么在整个「解空间」⾥⾯，设最终的结果是 ret ，于是有：
- 当 x ≤ ret 时， c ≤ M 。也就是「每次跳的最短距离」⼩于等于「最优距离」时，移⾛的⽯头块数「⼩于等于」 M ；
- 当 x > ret 时， c > M 。也就是「每次跳的最短距离」⼤于「最优距离」时，移⾛的⽯头块数「⼤于」 M 。
在解空间中，根据 的位置，可以将解集分成两部分，具有「⼆段性」，那么我们就可以「⼆分答 案」。
当我们每次⼆分⼀个最短距离 x 时，如何算出移⾛的⽯头块数 c ？
- 定义前后两个指针 i, j 遍历整个数组，设 i ≤ j ，每次 j 从 i 的位置开始向后移动；
- 当第⼀次发现 a[j] − a[i] ≥ x 时，说明 [i + 1, j − 1] 之间的⽯头都可以移⾛；
- 然后将 i 更新到 j 的位置，继续重复上⾯两步。
（3）参考代码
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 5e4 + 10;
LL l, n, m;
LL a[N];
// 当最短跳跃距离为 x 时，移走的岩石数目
LL calc(LL x)
{
LL ret = 0;
for(int i = 0; i <= n; i++)
{
int j = i + 1;
while(j <= n && a[j] - a[i] < x) j++;
ret += j - i - 1;
i = j - 1;
}
return ret;
}
int main()
{
cin >> l >> n >> m;
for(int i = 1; i <= n; i++) cin >> a[i];
a[n + 1] = l;
n++;
LL left = 1, right = l;
while(left < right)
{
LL mid = (left + right + 1) / 2;
if(calc(mid) <= m) left = mid;
else right = mid - 1;
}
cout << left << endl;
return 0;
}