本文主要是介绍二分（二段性），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本文用于记录个人算法竞赛学习，仅供参考
一.二分算法
二分算法一般用于具有二段性的问题，数据不一定具有单调性，所以单调可二分，可二分不一定就要单调。
二.整数二分
1. 模板一：将区间[l, r]划分为[l, mid] 和 [mid + 1, r], mid属于左区间，更新操作为r = mid 和 l = mid + 1; 计算mid 向下取整。
int bsearch_1(int l, int r)
{while (l < r){int mid = l + r >> 1;//check函数是处理逻辑if (check(mid))r = mid;elsel = mid + 1;}//最后l和r都指向同一个数，返回哪个都可以return l;
}
2.模板二：将区间[l, r]划分为[l ,mid - 1] 和 [mid + 1, r], mid 属于右区间，更新操作为r = mid - 1 和
l = mid; 计算mid时要+1向上取整避免死循环。
mid = (l + r + 1) >> 1避免死循环的逻辑是，假设剩余最后两个数，mid = l + r >> 1，那么mid = l，倘若mid对应值不是目标值,那么l = mid,这就形成闭环了，所以需要向上去取整。
int bsearch_2(int l, int r)
{while (l < r){int mid = (l + r + 1) >> 1;//check函数是处理逻辑if (check(mid))l = mid;elser = mid - 1;}return l;
}三.浮点数二分
double bsearch_3(double l, double r)
{// eps 表示精度，取决于题目对精度的要求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.浮点数二分
int main()
{int n;cin >> n;//由于c++浮点数存在精确度问题，当题目要求精确到几位数时，一般esp再往后取多两位double esp = 1e-8;double l = 0, r = n;while (r - l > esp){double mid = (l + r) / 2;if (mid * mid >= n)r = mid;elsel = mid;}printf("%lf\n", l);return 0;
}2.整数二分
P8647 [蓝桥杯 2017 省 AB] 分巧克力 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
根据题意得，需要找到符合条件的最大边长，假设这个边长是x，那么小于x的边长可以按要求分给每个小盆友（不是最大边长），大于x的边长不可能按要求平均分给小盆友，可以看出具有二段性，可以用二分，所以边长可以抽象成一条数轴，进而二分求得最大值。
#include <iostream>
#include <cstdio>
using namespace std;typedef long long LL;
int N = 100010;
int n, k;
int H[100010], W[100010];bool check(int mid)
{//统计饼干个数LL cnt = 0;for(int i = 0; i < n; i++){cnt += (LL)(H[i] / mid) * (W[i] / mid);}if(cnt >= k)return true;elsereturn false;
}int main()
{scanf("%d %d",&n, &k);for(int i = 0; i < n; i++){scanf("%d %d",&H[i],&W[i]);}int l = 0, r = 100010;while(l < r){int mid = l + r + 1 >> 1;if(check(mid))l = mid;elser = mid - 1;}printf("%d\n",r);return 0;
}这篇关于二分（二段性）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
