C++二分法_c++ 二分法

目录

1.理论背景

2.整数二分

2.1.在单调递增序列中找x或x的后继

2.2.在单调递增序列中找x或x的前驱

2.3.lower_bound与upper_bound

2.4.二分建模

3.实数二分

4.注

---

1.理论背景

假设我们有一个单变量的非线性方程 f(x) = 0，其中 f(x) 是一个连续函数。我们希望找到方程的根 x，使得 f(x) = 0。

1.搜索法：选择一个区间 [a, b]，使得 f(a) 和 f(b) 的符号相反。把区间[a,b]分成n等分，每个子区间长度为x，及算点xi=a+i*x(i=0,1,2,3...)的函数值f(xi)，若函数值为0，则为一个实数根，若满足f(xi)*f(xi+1)<0，则在区间(xi,xi+1)内至少有一个实数根，可以近似取(xi+xi+1)/2为近似根。

2.二分法可以用于逐步缩小根的搜索范围。基本思想如下：

1. 确定搜索范围的起始点和终止点。选择一个区间 [a, b]，使得 f(a) 和 f(b) 的符号相反。即 f(a) * f(b) < 0。
2. 计算区间的中点 c。可以使用 (a + b) / 2 的方式来计算中点。
3. 检查中点 c 的函数值 f(c) 与 0 的关系：
   • 如果 f(c) 等于 0，那么 c 就是方程的根，返回 c。
   • 如果 f(c) 与 0 的符号相反，那么根可能存在于区间 [a, c] 中，更新终止点为 c。
   • 如果 f(c) 与 0 的符号相同，那么根可能存在于区间 [c, b] 中，更新起始点为 c。
4. 重复步骤2和步骤3，直到找到一个满足精度要求的近似根。可以定义一个精度阈值，当区间的长度小于该阈值时，认为找到了满足要求的近似根。

需要注意的是，二分法对于非线性方程求解的成功与否取决于方程的性质和初始区间的选择。如果方程具有多个根或方程在某些区间上不满足单调性，那么二分法可能无法找到所有根或找到正确的根。在这种情况下，可能需要使用其他更复杂的数值方法来求解非线性方程。

算法竞赛中有两种二分题型：整数二分和实数二分

2.整数二分

向下取整，也就是更靠近left，为左中位数，mid=(left+right)/2;
向上取整，也就是更靠近rigth，为右中位数，mid=(left+riight+1)/2；

在单调递增序列中找x或x的后继，假设我们要找的整数 x 在序列中不存在，但存在一个比 x 稍大的数 y。如果我们使用向上取整，即取中间位置的上一个位置作为新的终止点，那么可能会错过 y，因为 y 可能正好位于中间位置的下一个位置。这样就无法找到大于等于 x 的最小整数。

而如果我们使用向下取整，即取中间位置的下一个位置作为新的起始点，那么无论 x 是否存在于序列中，都能保证我们找到大于等于 x 的最小整数。如果 x 存在于序列中，找到 x 后，返回该位置即可。如果 x 不存在于序列中，我们会找到大于 x 的最小整数，即 x 的后继。

因此，在单调递增序列中找 x 或者 x 的后继时，使用向下取整可以确保我们找到大于等于 x 的最小整数，从而得到正确的结果。

同理在单调递增序列中找x或x的前驱，适用于向上取整。

2.1.在单调递增序列中找x或x的后继

定义：在单调递增数列a[]中，如果有x，找到第一个x的位置；如果没有找到x，找到比x大的第一个数的位置。

示例a[]={-12,-6,-4,3,5,5,8,9) ，其中有n=8个数，存储在a[0]~a[7]。
(1)查找x=-5，返回位置2，指向a[2]=-4。
(2)查找x=7，返回位置6，指向a[6]=8。
(3)特别地，如果x大于最大的a[7]=9，如x=12，返回位置8。由于不存在a[8]，所以此时是越界的。关于如何编码，需要操作3个变量：区间左端点left、右端点right、二分的中位数mid，每次把区间缩小一半，把left或right移动到mid，直到left=right为止，即找到了答案所处的位置。
下面给出在单调递增序列中找r或x的后继的模板代码。整数二分法有很多编码方法，这里给出的区间是左闭右开的编码，即[0,8)。也可以直接对[o,n-1]区间二分，代码略有不同。虽然整数二分法的代码很短，但很容易出错。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int bin_search(int a[], int n, int x) {
	int left = 0, right = n;
	while (left < right) {
		int mid = (left + right) >> 1;//或者mid = (left + right) / 2
		if (a[mid] >= x) {
			right = mid;
		}
		else {
			left = mid + 1;
		}
	}
	return left;//或return right;
}
int main() {
	ios::sync_with_stdio;
	cin.tie(0);
	cout.tie(0);
	int n;
	int a[100];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int x;
	cin >> x;
	cout << bin_search(a, n, x);
	return 0;
}

当a[mid]≥x时，说明x在mid的左边或者x为mid此位置，新的搜素区间是左半部分，left不变，更新right=mid，因为mid有可能在mid的位置，所以right≠mid-1；
当a[mid]<x时，说明x在mid的右边，新的搜索区间是右半部分，right不变，更新left=mid+1；
此循环完毕后，left=right。

此代码left不能写成left=mid的原因：在实数二分中，确实是right=mid，left=mid。但是整数二分存在取整的问题，如原值left=2，right=3，计算得mid=(right+left)/2=2，若取left=mid，那么新值仍然是left=2，right=3，while()陷人了死循环。如果写成left=mid+1，就不会死循环。

2.2.在单调递增序列中找x或x的前驱

定义：在单调递增数列a[]中，如果有x，找到最后一个x的位置；如果没有找到x，找到比小的最后一个数的位置。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int bin_search(int a[], int n, int x) {
	int left = 0, right = n;
	while (left < right) {
		int mid = (left + right + 1) >> 1;//或者mid = (left + right + 1) / 2
		if (a[mid] <= x) {
			left = mid;
		}
		else {
			right = mid - 1;
		}
	}
	return left;//或者return right;
}
int main() {
	ios::sync_with_stdio;
	cin.tie(0);
	cout.tie(0);
	int n;
	int a[100];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int x;
	cin >> x;
	cout << bin_search(a, n, x);
	return 0;
}

当a[mid]>x时，说明x在mid的左边，新的搜素区间是左半部分，left不变，更新right=mid-1；
当a[mid]≤x时，说明x在mid的右边或者x为mid此位置，新的搜索区间是右半部分，right不变，更新left=mid，因为mid有可能在mid的位置，所以left≠mid+1；
此循环完毕后，left=right。

此代码right不能写成right=mid的原因与上一样。

2.3.lower_bound与upper_bound

数组a[]，长度为n，使用以下操作时需要先对a排序，sort(a,a+n)
lower_bound(a,a+n,x)  :返回第一个大于等于x的地址
upper_bound(a,a+n,x)  :返回第一个大于x的地址
则位置pos=lower_bound(a,a+n,x)-a or pos=upper_bound(a,a+n,x)-a

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
	ios::sync_with_stdio;
	cin.tie(0);
	cout.tie(0);
	int n;
	int a[100];
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	int x;
	cin >> x;
	cout << lower_bound(a, a + n, x) - a << endl;//输出第一个大于等于x的位置，即在单调递增序列中找x或x的后继
	cout << upper_bound(a, a + n, x) - a << endl;//输出第一个大于x的位置
	cout << upper_bound(a, a + n, x) - a - 1 << endl;//输出最后一个小于等于x的位置，在单调递增序列中找x或x的前驱
	cout << lower_bound(a, a + n, x) - a - 1 << endl;//输出最后一个小于x的位置
	return 0;
}
/*输入：
5
1 3 5 7 9
5
输出：
2
3
2
1
输入：
5
1 3 5 7 9
2
输出：
1
1
0
0*/

2.4.二分建模

while (left < right) {
	int ans;
	int mid = (left + right) / 2;
	if (check(mid)) {
		ans = mid;
		...//移动left或者right
	}
	else ...//移动right或者left
}

3.实数二分

实数上的二分比整数二分简单，不涉及取整问题，基本形式如下：

const double eps = 1e-7;//精度
while(right - left > esp) {
    double mid = (left + right) / 2;
    if((check(mid)) right = mid;
    else left = mid;
}

如果超时，则修改eps的值，使eps增大，例如可以让eps=1e-6；
如果答案错误，则可修改eps的值，使得eps减小，例如可以让eps=1e-8；

例题：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const double esp = 1e-7;
double s, a, b;
bool check(double mid) {
	int f = false;
	double t1 = mid / b;
	double t2 = (mid - t1 * a) / (a + b);
	if (t1 + (s - mid) / a >= t1 + t2 + (s - (t1 + t2) * a) / b) {
		f = true;
	}
	return f;
}
int main() {
	ios::sync_with_stdio;
	cin.tie(0);
	cout.tie(0);
	cin >> s >> a >> b;
	double right = 0, left = s;
	while (left - right > esp) {
		double mid = left + (right - left) / 2;
		if (check(mid)) right = mid;
		else left = mid;
	}
	printf("%.6f", left / b + (s - left) / a);
	return 0;
}

4.注

以上的mid均采用(left+right)/2，如果left+right超过了其类型的范围，则可改为，mid=left+(right-left)/2。