二分法
整数二分
本质
- 二分法的本质不是单调性而是二段性，一段满足性质，一段不满足性质。两个模板分别在满足性质的区间里寻找最左边的答案(一)和最右边的答案(二)
- 有单调性一定可以二分，能二分不一定要有单调性
- 每次二分要保证mid处于答案的区间内
- 二分模板在有解的情况用，无解下二分的输出根据题目确定
模板
版本1
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。
1
2
3
4
5
6
7
8
9
10
| int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
|
模板一在保证有解的情况下逐步向左缩小区间
版本2
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;
此时为了防止死循环，计算mid时需要加1。
1
2
3
4
5
6
7
8
9
10
| int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
|
模板二在保证有解的情况下逐步向右缩小区间
例子
1
2
3
| 1 2 2 3 3 3 4 4 5 用二分法寻找等于3的位置
模板一check函数为x>=3 输出3
模板二check函数为x<=3 输出5
|
浮点数二分
有for和while两种写法
1
2
3
4
5
6
7
8
9
10
11
12
13
| bool check(double x) {}
double bsearch_3(double l, double r)
{
const double eps = 1e-6;
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return 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
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <bits/stdc++.h>
using namespace std;
const int N = 17;
const double eplison = 1e-5;
double a[N];
int n;
double cal(double x) {
double t = 1;
double ans = (double )0;
for (int i = n; i >= 0; i--) {
ans += t * a[i];
t *= x;
}
return ans;
}
int main() {
double l, r;
scanf("%d%lf%lf", &n, &l, &r);
for (int i = 0; i <= n; i++) {
scanf("%lf", &a[i]);
}
while (r - l > eplison) {
double mid = (l + r) / 2;
double lmid = mid - eplison;
double rmid = mid + eplison;
if (cal(lmid) > cal(rmid)) {
r = mid;
} else {
l = mid;
}
}
cout << l << endl;
return 0;
}
|
