引言
笼统概括：二分算法把一个区间对半分成两部分，按某种性质每次只取一部分。然后将取的那部分再次对半分，如此往复。直到区间只剩一个数。
细心的小伙伴会对上面的加粗的字有所警觉。
对半分 ? 整数能每次都对半分吗？奇数怎么办？这涉及向上向下取整。
某种性质 ？例如 ">=x" 为一种性质，这样把区间分成 "<x" 和 ">=x" 。
只剩一个数 ? 浮点数怎么可能只剩一个数？这涉及精度问题。
整数二分（~手动音效）
真正二分之前，其实按照题目的具体意思，已经对区间按性质划成了两部分。
事实上，能二分也就意味着能对区间按某种性质划出两部分
例1，求某个有序区间第一个>=3的数
{1, 2, 3, 3, 4, 5} 按照">=3" 划出 {1, 2} 和 {3, 3, 4, 5}
例2，求某个有序区间最后一个<=3的数
{1, 2, 3, 3, 4, 5} 按照"<=3" 划出 {1, 2, 3, 3} 和 { 4, 5}
不管题目要求的性质是什么，对半后再按某种性质取“一半”区间，
取到最后会发现，只会取到两个数。
哪两个数? 按照性质划分成两区间，不妨叫第一区间和第二区间（或者绕一点叫左右区间）
只能取到第一区间（左区间）的右端点，
即例1中{1, 2}的2 ， 例2中 {1, 2, 3, 3}的3
和第二区间（右区间）的左端点，
即例1中 {3, 3, 4, 5}的3， 例2中{ 4, 5} 的4
之后再按照题目的要求，该取啥就取啥，完事~。
实际上整数二分成了求解某个区间某个端点的方法
对应不同两个端点就会有两个模板。
求第一区间（左区间）的右端点模板
bool check(int x) {/* ... */} // 若 q[x] <= 某个点 return ture;反之
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
int bsearch_1(int l, int r)
{
while (l < r)//不断递归,最终l == r
{
int mid = l + r + 1>> 1; // 两个数时,若l + r >> 1,mid = l, l = l,无限划分,错误
if (check(mid)) l = mid; //从左向右缩小区间。l要+1
else r = mid - 1; // 记住l最后都比r大
}
return l;
}
求第二区间（右区间）的左端点模板
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
bool check(int x) {/* ... */} // 若 q[x] <= 某个点 return ture;反之
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;// 两个数时,若l + r + 1>> 1,mid = r, r = r,无限划分,错误
if (check(mid)) r = mid;//从右向左缩小区间。r不用+1
else l = mid + 1;// 记住l最后都比r大
}
return l;
}
浮点二分（~手动音效）
不同与整数二分，浮点二分理论上可以无限对半分。（牛~）
但我们不需要它无限分，这没有意义啊~ （叹~）
对半分到什么时候？
- 给它下个次数指标，你，给小爷我对半分个一百次。（好勒~）
- 下个精度限制，随便你对半分多少次，只要满足精度要求，随便分。(行~)
而且浮点二分比较专一，只找一个数，不用像整数二分那样各种边界处理的。
简单！(整数二分：我也不想~~)
同样的，按照某个性质，区间分成两个部分。
而第一区间（左区间）的右端点 和 第二区间（右区间）的左端点 等同为一个。
那只需要一个模板就好了
精度要求浮点二分模板
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求
//求保留6位就>1e-8 保留 4位就1e-6 差两位，比要求的位数多二
while (r - l > eps)
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
次数要求浮点二分模板
bool check(double x) {/* ... */} // 检查x是否满足某种性质
double bsearch_3(double l, double r)
{
for(int i = 0; i < 100; i ++ );
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
