当前位置：首页 > news >正文

基础算法 —— 二分算法【复习总结】

news 来源：原创 2025/8/12 13:50:20

1. 简介

1.1 原理

二分算法，顾名思义，关键在于二分，当我们求解的目标具有二段性时，我们就可以使用二分算法：

先根据待查找区间中点位置，判断结果会在左侧还是右侧，接下来，舍弃一半的查找区间，在结果存在的区间继续进行二分查找

1.2 模板

二分查找可以分为：1. 二分查找区间左端点；2. 二分查找区间右端点

（ “左端点”指当结果存在多个，我们选择最靠左边的那一个；“右端点”指当结果存在多个，我们选择最靠右边的那一个）

如：在序列 1 2 3 4 4 5 5 5 6 6 7 8 9 9 10 中，求大于等于4的数，我们选绿色左端点；求小于等于10的数，我们选黄色右端点

// 二分查找区间左端点
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;
}
// 注1：二分结束后可能要判断是否存在结果
// 注2：如果结束条件为 l<=r，可能会导致死循环
// 注3：可以快速记忆：a. 求左端点，mid=(l+r)/2;求右端点，mid=(l+r+1)/2。因为+1导致结果偏右
//                    b. if/else中出现 -1 ，求 mid 就要 +1
// 注4：为防止溢出，求中点时：mid=l+(r - l)/2

1.3 STL中二分查找

头文件：<algorithm>
1. lower_bound：大于等于x的最小元素，返回的是迭代器
2. upper_bound：大于x的最小元素，返回的是迭代器。
二者都用二分实现。但是STL中的二分查找只能适用于【在有序的数组中查找】

2. 二分查找

2.1 高考志愿

2.1.1 题目描述

有 m 所学校，每所学校预计分数线是 a[i]。有 n 位学生，估分分别为 b[i]。

根据 n 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小，这个最小值为不满意度。求所有学生不满意度和的最小值。

输入描述：

第一行读入两个整数 m,n。m 表示学校数，n 表示学生数。

第二行共有 m 个数，表示 m 个学校的预计录取分数。第三行有 n 个数，表示 n 个学生的估分成绩。

（1≤n,m≤1e5）

输出描述：

一行，为最小的不满度之和。

2.1.2 算法分析

先把学校的录取分数排序，根据每个学生的成绩 b ，在【序列】中二分查找第一个 >= b 的位置pos , 差值可能是正数或者负数，所有差值最小的结果在 pos 位置或 pos-1 位置（选择最接近的）

但注意：1. 如果所有的录取成绩都大于 b，pos - 1 会在0下标，访问一个无效值，结果可能错误

2. 如果所有的录取成绩都小于 b，pos 会在n下标，对于此题无影响

针对这种情况，我们可以添加【左右护法】，即在序列左右添加不会对结果造成干扰的值，确保pos和pos-1有效（这个左右护法一般是正无穷或者负无穷）

对于该题，我们添加左护法即可

2.1.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) left = mid + 1;else right = mid;}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 x; cin >> x;int pos = find(x);ret += min(abs(a[pos] - x), abs(a[pos - 1] - x));}cout << ret << endl;return 0;
}

3. 二分答案

3.1 简介

二分答案是二分查找的抽象化，准确说应叫【二分答案+判断】

⼆分答案用来处理大部分「最大值最小」以及「最小值最大」的问题。即解空间在从小到大的变化中，「判断」结果会出现「⼆段性」，此时我们就可以「二分」这个解空间，得到答案

3.2 例题

3.2.1 砍树

3.2.1.1 题目描述

伐木工要砍 M 米长的木材。但他只被允许砍伐一排树。

伐木工的伐木流程如下：设置一个高度参数 H（米），伐木机升起一个巨大的锯片到高度 H，并锯掉所有树比 H 高的部分（树木不高于 H 米的部分保持不变）。例如，如果一排树的高度分别为 20,15,10 和 17，锯片升到 15 米的高度，切割后树木剩下的高度将是 15,15,10 和 15，而伐木工将从第 1 棵树得到 5 米，从第 4 棵树得到 2 米，共得到 7 米木材。

伐木工不会砍掉过多的木材。这也是他尽可能高地设定伐木机锯片的原因。请找到伐木机锯片的最大的整数高度 H，使得伐木工能得到的木材至少为 M 米。换句话说，如果再升高 1 米，他将得不到 M 米木材。

输入描述：

第 1 行 2 个整数 N 和 M，N 表示树木的数量，M 表示需要的木材总长度。（1≤N≤1e6，1≤M≤2×1e9 ，树的高度 ≤4×1e5，所有树的高度总和 >M)

第 2 行 N 个整数表示每棵树的高度。

输出描述：

1 个整数，表示锯片的最高高度。

输入：

4 7
20 15 10 17

输出：

3.2.1.2 算法思想

假设伐木机高度为 H 时,得到木材为 sum，最终锯片的高度为 ret 。

根据题意，当 H<=ret 时，sum>=M ；当 H>ret 时，sum<M 。即【伐木机的高度】小于【最优高度】时，得到的木材大于 M ,我们就是在保证木材大于 M 的情况下求得最高高度。这就是【最小值最大】（伐木机高度从小到大寻找最合适的）

3.2.1.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++){// 针对每根木头，切成的木材为 a[i]-xif (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){int mid = (left + right + 1) / 2;if (calc(mid) >= m) left = mid;else right = mid - 1;}cout << left << endl;return 0;
}

3.2.2 跳石头

3.2.2.1 题目描述

现要进行跳石头比赛，组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。

输入描述：

第一行包含三个整数 L,N,M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L≥1 且 N≥M≥0。( 0≤M≤N≤5e4,1≤L≤1e9)

接下来 N 行，每行一个整数，第 i 行的整数 D[i](0<Di<L)，表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

输出描述：

一个整数，即最短跳跃距离的最大值。

输入：

25 5 2
2
11
14
17
21

输出：

3.2.2.2 算法思想

假设每次跳的最短距离为 x ,移走的石头数为 sum ,最终最短跳跃距离的最大值为 ret

根据题意，当 x<=ret 时，sum<=M;当 x>ret时，sum>M。即【每次跳的最短距离】小于【最优距离】时，移走的石头数小于 M,我们就是在保证移走的石头数小于 M 的情况下求得【最短跳跃距离最大值】。这就是【最小值最大】（移走的石头从小到大寻找最合适的）

对于如何计算当二分一个最短距离 x 时，移动的石头数：

此时我们可以结合我们上一篇所介绍的【双指针】，我们可以定义两个指针 left 和 right ，当第一次出现 a[right]-a[left] >= x 时，[ left+1,right-1 ] 中的所有石头都可以移走（因为之间所有石头距离都小于 x ,不符合题意)。之后将 left 更新到 right 位置。然后 right 向后移动。重复此过程（简单模拟一下还是很容易理解）

3.2.2.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;// 下标0为起点for (int left = 0; left <= n; left++){int right = left + 1;while (right <= n && a[right] - a[left] < x) right++;ret += right - left - 1;left = right - 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;
}

1. 简介

1.1 原理

1.2 模板

1.3 STL中二分查找

2. 二分查找

2.1 高考志愿

2.1.1 题目描述

2.1.2 算法分析

2.1.3 代码实现

3. 二分答案

3.1 简介

3.2 例题

3.2.1 砍树

3.2.1.1 题目描述

3.2.1.2 算法思想

3.2.1.3 代码实现

3.2.2 跳石头

3.2.2.1 题目描述

3.2.2.2 算法思想

3.2.2.3 代码实现

相关文章：