二分
题单介绍
# 二分题单
难度： 从橙~蓝
时间：两周以内
## luogu题目：
- 橙 [P1102](https://www.luogu.com.cn/problem/P1102) [P1678](https://www.luogu.com.cn/problem/P1678) [P1824](https://www.luogu.com.cn/problem/P8814) [P1873](https://www.luogu.com.cn/problem/P1873) [P1918](https://www.luogu.com.cn/problem/P1918)
- 黄 [P2440](https://www.luogu.com.cn/problem/P2440) [P2678](https://www.luogu.com.cn/problem/P2678) [P3853](https://www.luogu.com.cn/problem/P3853) [P1182](https://www.luogu.com.cn/problem/P1182) [P3743](https://www.luogu.com.cn/problem/P3743) [P1843](https://www.luogu.com.cn/problem/P1843) [P2985](https://www.luogu.com.cn/problem/P2985)
[P2920](https://www.luogu.com.cn/problem/P2920)
[P10450](https://www.luogu.com.cn/problem/P10450)
- 绿 [P4047](https://www.luogu.com.cn/problem/P4047) [P4447](https://www.luogu.com.cn/problem/P4447)
- 蓝 [P1800](https://www.luogu.com.cn/problem/P1800) [arc079C](https://www.luogu.com.cn/problem/AT_arc079_c)
## AcWing题目：
[790](https://www.acwing.com/problem/content/792/) [102](https://www.acwing.com/problem/content/104/) [789](https://www.acwing.com/problem/content/791/)
## 注：
1. 蓝题及以上选做
2. [P8814](https://www.luogu.com.cn/problem/P8814) 选做 (需数学功底较强)
3. 可以先做AcWing 789和790 模板题
4. P1918数据是无序的，可以用STL
## 整数二分模板
```cpp
bool check(int x)
{
//检查x是否满足某种性质
}
//区间[l,r]被划分成[l,mid]和[mid+1,r]时使用:
// (左区间满足，右区间不满足)
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;
}
//区间[l,r]被划分成[l, mid- 1]和[mid,r]时使用:
// (左区间不满足，右区间满足)
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1;//如果下方else后面是l则这里加l
if (check(mid)) l = mid;
else r = mid - 1;//左加右减
}
return l;
}
/*
模板一
我们最终要找的边界是一个性质在右半区符合，在左半区不符
合的性质。我们要找符合的右半区的左边界点。管中窥豹的判断check（mid）,如果mid符合条件Mid是在右半区符合性
质的半区中。要找左边界点的范围则更新为r = mid（包含
Mid）。如果mid不符合条件，我们要找符合性质的左端点则l
= mid + 1（已经确定mid是不符合的就从mid+1开始算）
模板二
我们最终找的边界是一个性质在右半区不符合，在左半区符合
的性质。并找到符合性质的左半区的右边界点。对mid进行判
断来获得结果：如果mid符合条件，则mid就在左半区，那么
我们要找的右边界点就可以更新为（mid,r）l = mid。
如果mid不满足条件，则mid必然在右半区间，而我们要找的
符合要求的左半区间性质的右端点就是（l,mid-1）。r = mid - 1;
*/
```
其实从AcWing 789，790两题看，如果找最大，用模板2，反之，用模板1
## 浮点数二分模板
```cpp
bool check(double x)
{
// 检查某种性质
}
double bsearch_3(double l, double r)
{
while (r - l > eps) // eps为精度
{
double mid = (l + r) / 2;
if (check(mid)) r = mid;
else l = mid;
}
return l;
}
double bsearch_4(double l, double r)
{
while (r - l > eps) // eps为精度
{
double mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
return l;
}
```
## STL中的lower_bound与upper_bound
* lower_bound 是 C++ 标准模板库（STL）中的一个算法，用于在有序范围内查找第一个大于或等于给定值的元素。
```cpp
// STL容器用法
auto it = lower_bound(vec.begin(), vec.end(), val, /*cmp*/);
// 这里实际存的是地址
// int i = *it
// 数组用法
auto it = lower_bound(vec + 1, vec + 1 + n, val, /*cmp*/);
// 如果要查找下标
int pos = lower_bound(vec + 1, vec + 1 + n, val, /*cmp*/) - vec;
```
* upper_bound别的用法都相同，只不过是查找大于val的第一个元素
## 二分三步法
1. 确定枚举的东西和模板
2. 判断，也就是check函数判断的依据
3. 找到对应关系