二分法求答案

定义

对某一区间 [l, r], 不断进行「一分为二」划分 mid = (l + r) / 2, 使得区间端点不断逼近所求答案

基本应用: 二分查找

定义: 对有序的数据, 使用二分法, 查找目标值
代码: ``` l = 0, r = max; //左右端点 while (l <= r) { mid = (l + r) >> 1; //一分为二求中点 if (mid > x) { //如果中点大于目标值则更新右边界
```
 r = mid  - 1;
```
} else if (mid < x) { //如果中点小于目标值则更新左边界
```
 l = mid + 1;
```
} else { //相等则结束查找
```
 break;
```
} }

### 二分求答案
1. 问题: 求满足某一条件的最大(小)值
- 最大的最小值 / 最小的最大值
- 最逼近某一个值的最小(大)值
1. 方法: 把求最优解的问题，转化为给定一个值 mid ，判定是否存在一个方案，达到 mid 的的问题。(二分答案转化为判定)。
1. 两种区间:
- [l, mid - 1], [mid, r]: 最大的最小值
- [l, mid], [mid + 1, r]: 最小的最大值
- 记忆方法: 可以把mid当作那个目标值, 求最大化, mid在右边, 求最小化, mid在左边, 来以此划分区间
1. 模板

//check为检查是否满足条件, 为重难点 //传入的参数 l , r 最好是题目数据范围偏差一点 , 比如 l = min - 1, r = max + 1 //第一种求最小的最大值 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; //return l 或者 return r 都一样, 因为最后结束循环肯定是 l = r } //第二种求最大的最小值 int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; //此处mid要加一再划分为二, 防止死循环 if (check(mid)) l = mid; else r = mid - 1; } return l; }


5. 补充 浮点数二分

//浮点数不能用位运算符 double bsearch_3(double l, double r) { const double eps = 1e-6; // eps 表示精度，取决于题目对精度的要求，要保留几位几位 while (r - l > eps) { double mid = (l + r) / 2.0; if (check(mid)) l = mid; else r = mid - 1; } return l; }

```