二分法——《算法笔记》

发表于 | 分类于 | 浏览次数
字数统计: 1,262 字 | 阅读时长 ≈ 5 分钟

1. 二分法适用范围

二分法适用在一个严格单调序列中找到给定的某个数。

2. 二分法模板提要

首先，在库中的有lower_bound()和upper_bound()两个函数，对于lower_bound()来说，它是寻找第一个满足条件“值大于等于x”的元素的位置；而对于upper_bound()来说，它是寻找第一个满足条件“值大于x”的元素的位置。对于此类寻找有序序列中第一个满足某条件的元素的位置的问题，有固定的模板，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//二分区间位左闭右闭的[left, right]，初值必须能覆盖解的所有可能取值
int solve(int left, int right)
{
	int mid;
	while (left < right) //对于[left, right]来说，left == right意味着找到唯一位置
	{
		mid = (left + right) / 2;
		if (条件成立) //条件成立，第一个满足条件的元素的位置<=mid
		{
			right = mid; //往左子区间[left, mid]寻找
		}else //条件不成立，则第一个满足该条件的元素的位置>mid
		{
			left = mid + 1;//往右子区间[mid+1, right]寻找
		}
	}
	return left; //返回最终确定的位置
}

另外，如果想要寻找最后一个满足”条件C“的元素的位置，则可以先求第一个满足”条件!C“的元素的位置，然后将该位置减1即可。我们也可以把上述模板改成左开右闭的二分区间来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//二分区间位左开右闭的(left, right]，初值必须能覆盖解的所有可能取值，并且left比最小值小1
int solve(int left, int right)
{
	int mid;
	while (left + 1 < right) //对于(left, right]来说，left + 1== right意味着找到唯一位置
	{
		mid = (left + right) / 2;
		if (条件成立) //条件成立，第一个满足条件的元素的位置<=mid
		{
			right = mid; //往左子区间(left, mid]寻找
		}else //条件不成立，则第一个满足该条件的元素的位置>mid
		{
			left = mid ;//往右子区间(mid, right]寻找
		}
	}
	return right; //返回最终确定的位置
}

3. 模板题

3.1 木棒切割问题

给出长度已知的 n 根木棒，每根木棒的长度可能不同，现在希望通过切割它们得到至少 k 段长度相等的木棒（长度必须为整数），问这些长度相等的木棒最长能有多长。

根据题意可知，长度相等的木棒的长度 L 越长，可得到的长度相等的木棒的段数越少，因此这是一个单调的情况，可以二分木棒长度 L ，当最后刚好可得到 k 段木棒时的 L 值即为所求最大长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
 
using namespace std;
 
int len[100];
 
int main() {
	int n, k;
	cin >> n >> k;
	int right = 0;
	for (int i = 0; i < n; i++) {
		cin >> len[i];
		if (len[i] > right) right = len[i];
	}
	int left = 1; right++;
	while (left + 1 < right) {
		int mid = (left + right) / 2;
		int t = 0;
		for (int i = 0; i < n; i++)
			t += len[i] / mid;
		if (t < k) right = mid;
		else left = mid;
	}
	cout << right - 1 << endl;
	return 0;
3.2 凸多边形的最大外接圆

给出 n 个线段的长度，试将他们头尾相接（顺序任意）地组合成一个凸多边形，使得该凸多边形的外接圆（即能使凸多边形的所有顶点都在圆周上的圆）的半径最大，求该最大半径。n 不超过 $10^{5}$，线段长度均不超过100，要求算法中不涉及坐标的计算。

对于要求的半径，当半径过小时，所有线段首位相连放在圆里面形成 n 个弦，弦所对的圆心角之和大于 360°，而当半径过大时，弦所对的圆心角之和小于360°。仔细思考，圆心角之和与对应半径是一个单调的关系，因此可以采用二分法解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<math>
 
const double pi = acos(-1);
const double eps = 1e-5;
 
using namespace std;
 
double m[100005];
 
int main() {
	int n;
	double min = 101, max = 0, r;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> m[i];
		if (m[i] < min) min = m[i];
		max += m[i];
	}
	min /= 2;
	while (min < max) { //左闭右闭
		r = (min + max) / 2;
		double degree = 0;
		for (int i = 0; i < n; i++)
			if (m[i] > 2 * r) {
				degree = pi + 1;  //存在一条弦的长度大于两倍半径，这种情况不可能发生，所以当前的半径r过小，要到其右子区间进行搜索
				break;
			}
			else degree += asin(m[i] / 2 / r); //求得所有弦对应的圆心角之和
		if (fabs(degree - pi) < eps) break; //若圆心角之和等于360°，此时的r即为正确答案
		else if (degree > pi) min = r;//大于360°，要到其右子区间[r, max]进行搜索
		else max = r; //否则，要到其左子区间[min, r]进行搜索。
	}
	cout << r << endl;
	return 0;
}