二分
V_Me_50
·
·
个人记录
二分
二分
适用于一类具有单调性的问题。
二分查找
例题 1：递增序列二分查找
洛谷 T164755 整数查找
模型：根据大小关系可将序列分为三个部分：
标程：[整数查找](https://paste.ubuntu.com/p/wxqHRQ97dg/)
### 例题 2：非减序列二分查找
[洛谷 T164761 整数插入](https://www.luogu.com.cn/problem/T164761)
模型：在非减序列中查找$ \ge x $的数的第一次出现位置，可以将序列看作为 $0,1 $的两段，相当于查找分界线。
## 几种模型：
+ 在非减序列中查找 $\ge x$ 的数的第一次出现位置。
+ 在非减序列中查找 $\gt x$ 的数的第一次出现位置。
+ 在非减序列中查找 $\le x$ 的数的最后一次出现位置。
+ 在非减序列中查找 $\lt x$ 的数的最后一次出现位置。
+ 递减序列和非增序列同理。
## 二分答案
原问题可以找到一个单调函数，答案可以分为使原问题有解$（1）$和无解$（0）$的两段，那么相当于查找分界线。
本质仍是二分查找并判断问题是否有解。
### 例题 1：整数域上的二分答案
[洛谷 P1182 数列分段](https://www.luogu.com.cn/problem/P1182)
思路：当每段和的最大值 $xx$ 越大，数列能够分成的最少段数 $(x)$ 越小，求使 $f(x) \lt mf(x)<m $的最小整数 $xx$。
模型：随着 $x$ 的增大，原问题有解情况为 $0-1$ 分段，查找 $\ge 1$ 的最小整数 $x$。
### 例题 2：实数域上的二分答案
[洛谷 P1163 银行货款](https://www.luogu.com.cn/problem/P1163)
二分的答案从整数域变为实数域，需要考虑精度问题。精度一般设置为 $10^{-x -2}$其中$ x $为题目要求的精度。
提示：当利率为 $x$ ，每月分期金额为 $A$，偿还贷款 $M$ 月时，本金:$\sum\limits^M_{i=1}A*(\frac{1}{1+x})^i