二分与三分-尧图网络科技

二分

二分基本思想与二分查找

二分，顾名思义，就是把一个东西分成两部分。

对于任意的序列上元素的查询，我们只能一个个的枚举。而当序列有序时，我们便可以使用二分进行优化。

具体的，我们用 $[l,r]$ 表示当前查找的区间，每次取其中点 $mid$，比较 $mid$ 处的值与所查询值的大小。由于序列有序，此时答案一定可以确定在其中一半上。
代码如下：

inline int find1(int l, int r, int x){while(l<r){int mid=(l+r)>>1;if(a[mid]>=x) r=mid;// 在左区间else l=mid+1;// 在右区间}return l;
}

可以发现，这样我们找到的，实际上是元素 $x$ 第一次出现的位置，如果序列中没有 $x$，我们找到的是“ $\ge x$ 的最小值”。

类似的，我们也可以找 $x$ 最后一次出现的位置，即“ $\le x$ 的最大值”：

inline int find2(int l, int r, int x){while(l<r){int mid=(l+r+1)>>1;if(a[mid]<=x) l=mid;else r=mid-1;}return l;
}

时间复杂度显然为为 $O(\log n)$ 。

需要注意的实现细节：

求 $mid$ 时，用右移运算，不要用c++的除法运算，因为后者是向0取整，而前者是严格下取整。两者的区别： $(-3)/2=-1, (-3)>>1=-2$ 。在涉及负数时右移能正常跑，除法会出玄学错误。
注意求 $mid$ 、取左右区间时 $+1,-1$ 的问题。这里建议直接背过板子，不建议手推，如果错误了很容易死循环或者漏解。

二分答案

事实上，二分还可以求解许多带约束条件的、满足“单调性”的东西的最值。

所谓“单调性”，是指一个东西 $y$ 的影响因素 $x$ 增大时，$y$ 一定跟着增大（或减小）。

此时便可使用二分，这样就相当于以 $x$ 为下标，$y$ 为数组元素，在上面查找。

与二分查找一样，还是维护答案区间 $[l,r]$ 并取其中点 $mid$。

如果我们能够判断mid是否合法，那么，我们就可以由答案单调性确定答案处于哪一半，不断缩小区间逼近最优解，直到左右指针相等，我们就得到了最终答案。

具体的，假如我们要求一个东西的最小值，它满足单调递增性。

现在我们二分出一个 $mid$，假设我们已经判断出它是否合法。如果合法，则考虑往小里找更小值，取左区间。

否则，意味着 $mid$ 小的过头了，需要往大里找，取右区间。

这样便可求得答案。时间复杂度 $O(k \log M)$ ，其中 $k$ 为判断答案是否合法的时间，$M$ 为答案的规模。

容易发现，二分答案过程中，“求中点”“取左右区间”等二分框架和普通二分查找没有区别，只需将if判断条件改为判断是否合法的函数即可。

所以在二分答案题目中，需要脑子思考的仅仅是“如何判断合法性”这一点。因此，我们通过二分答案，将求解性问题转化为了判定性问题，简化了题目的求解。

如何判断一个东西是否可以用二分呢？

首先，看要求啥，一般是求...的最大值或最小值，特别明显的像“...的最大值，最小是多少”这种字眼，基本上不用多想，就可以考虑二分了。而像求...的方案数这种就不常用用二分直接求解，但不一定用不到二分。

然后判断答案是否具有单调性。如果你觉得单调性这个词过于抽象，可以这么想：“如果判断出mid是否合法，能否将答案确定在某一半区间内？”。

最后，考虑一个高效的判定方法，并计算复杂度，看能否通过这个题的数据。

Maximize the Gap - AtCoder abc463_d

这就出现了非常明显的“最大化最小值”，直接考虑二分。

首先判断单调性。不难发现得分越大，能选择的区间的数量越少，于是答案有单调性，满足二分的前提。由于要求最大值，于是我们使用第最大值板子。

二分出一个可能的“得分”$mid$，我们尝试贪心的找是否存在一种方案满足条件。

对所有的区间按右端点从小到大排序，显然，如果两个区间都可以被选，那么右端点小的一定优先选，因为选右端点小的可以为后面的区间留下更多的机会，这样的答案一定不劣于选右端点大的区间。

从第一个区间开始选，如果当前区间和上一个被选的区间的距离 $\ge mid$，则这个区间是可行的，把它选上。

最后比较选择的区间个数 $cnt$ 与 $k$ 的大小，如果 $cnt \ge k$ 说明答案可行，取右半区间。否则答案太大，取左区间。

为什么 $\ge k$ 说明答案满足条件

如果能选超过 $k$ 个区间满足条件，那么从中去掉几个区间也一定满足条件，所以一定可以满足题目要求的 $k$ 个区间。

如果连 $k$ 个区间都选不出来，那就说明这个答案不行，得换一个。

时间复杂度 $O(n \log V)$。

点击查看代码

#include<bits/stdc++.h>
#define st first
#define nd second
using namespace std;const int N=5e5+10;
pair<int,int> a[N];
int n,k,ans;inline bool cmp(pair<int,int> _, pair<int,int> __){return _.nd<__.nd;
}inline bool pd(int x){int lst=a[1].nd, cnt=1;for(int i=2; i<=n; i++){if(a[i].st>lst){if(a[i].st-lst>=x){cnt++;lst=a[i].nd;}}}return cnt>=k;
}signed main(){cin.tie(0)->sync_with_stdio(0);cin>>n>>k;int l=1,r=0 ;for(int i=1; i<=n; i++)cin>>a[i].st>>a[i].nd, r=max(r,a[i].nd);stable_sort(a+1, a+n+1, cmp);while(l<r){int mid=(l+r+1)>>1;if(pd(mid)) l=mid;else r=mid-1;}if(pd(l)) cout<<l;else cout<<-1;return 0;
}

P1314 [NOIP 2011 提高组] 聪明的质监员

不难注意到，$W$ 越大，$y_i$ 就越小，因此 $y$ 也变小，于是有单调性，可以二分。

于是，我们二分 $W$，结合前缀和快速求出 $y$。如果 $y\le s$，为了使答案更优，我们想让 $y$ 增大，也就是让 $W$ 减小，所以取左区间，反之取右区间。

这里需要注意的是，我们并不能保证二分结束后的 $l$ 就是最优取值，所以我们必须在二分中对所有算出来的 $y$ 都求一遍 $|y-s|$ 然后取 $\min$。

记得每次算 $y$ 之前都要对前缀和数组清空。

另外，本题的二分上界至少需要大于所有的 $w[i]$，不要开小了。

点击查看代码

#include<bits/stdc++.h>
#define int long long// 不开___见祖宗
using namespace std;const int N=2e5+10;
struct Segment{int l,r;}a[N];
int w[N], v[N], sum[N], cnt[N];
int n,m,ans=1e18,s;inline int calc(int x){fill(sum, sum+n+1, 0); fill(cnt, cnt+n+1, 0);// fill比循环赋值快，能赋任意值，不会像memset一样被某些题卡for(int i=1; i<=n; i++){// 注意前缀和不要写错sum[i]=sum[i-1]; cnt[i]=cnt[i-1];if(w[i]>=x)sum[i]+=v[i], cnt[i]++;}int y=0;for(int i=1; i<=m; i++){y+=(cnt[a[i].r]-cnt[a[i].l-1]) * (sum[a[i].r]-sum[a[i].l-1]);}ans=min(ans, abs(y-s));return y;
}signed main(){cin.tie(0)->sync_with_stdio(0);cin>>n>>m>>s;int l=0,r=0;for(int i=1; i<=n; i++){cin>>w[i]>>v[i];r=max(r,w[i]);}r++;// 二分上界要大于所有的w[i]for(int i=1; i<=m; i++){cin>>a[i].l>>a[i].r;}while(l<r){int mid=(l+r)>>1;if(calc(mid)<=s) r=mid;else l=mid+1;}cout<<ans;return 0;
}

二分对其他算法的优化

P1020 [NOIP 1999 提高组] 导弹拦截

第一问非常板子的最长不升子序列。第二问有点难搞，如果你知道狄尔沃斯定理就可以知道，答案就是最长上升子序列。证明不太容易，感性理解即可。

求LIS就非常简单了。令 $f[i]$ 表示以 $i$ 为结尾的LIS长度，很容易得出转移方程：

\[f[i]=\max_{j \le i,a[j]<a[i]}\{f[j]+1\} \]

美滋滋的写代码，突然发现：复杂度不对啊，这不 $O(n^2)$ 的吗？

考虑对其进行优化。由于 $f$ 不满足单调性，所以不能直接二分。

假设我们现在求出来了许多长度均为l的LIS，其结尾值不同，我们应该取哪一个？

贪心的想，肯定取结尾更小的，因为结尾越小，求更长的LIS时可以使得别的元素进入LIS的机会更多。

于是我们用 $g[i]$ 表示长度为 $i$ 的LIS的最小结尾元素，显然，$g[i]$ 单调不降。

于是，我们还是用一遍循环 $i:[1,n]$ 来求解 $f[i]$。

假设当前循环到 $i$，则此时 $g$ 中存储的便是 $1$ ~ $i$ 中所有可能长度的LIS的结尾最小值。

定义 $len$ 表示当前求出的最长LIS的长度，二分查找在 $[1,len]$ 中，最大的 $p$ 使得 $g[p]<a[i]$ ，则 $f[i]=p+1$ 。

求完 $f$ 后，接着更新 $g$，即 $g[p+1]=a[i]$。

由此便可在 $O(n\log n)$ 的复杂度内求解LIS。

实数二分

同整数域类似的，我们也可以可以在实数域上完成二分。

实数二分的板子和整数二分略有不同，有很多坑点，以求平方根为例，如下：

const double eps=1e-10;// 一般取 10^-(保留小数点后位数+2)
// 注意千万不要写const int eps
inline double Sqrt(double x){// 全是double，不要写成intdouble l=0, r=max(1.0,x);// 处理小于1的数的开根while(l+eps<r){// 避免精度误差double mid=(l+r)/2;if(mid>x/mid) r=mid;// 防溢出else l=mid;// 不需要+1或-1}return l;
}// 加个-Wconversion可以有效避免把double打成int的错误。

P1024 [NOIP 2001 提高组] 一元三次方程求解

由高中数学人教A版必修一第四章指数函数与对数函数中的某一页可知，求函数的零点可以用二分法。思路很简单，取中间点 $mid$，由零点存在定理判断零点在哪一边，我们就取哪一半区间。

虽然二分经常和单调性挂钩，但书中并没有强调所求函数为单调函数。事实上，实数二分也可以求非单调函数的零点，但这对函数有一个要求：零点有且只能有一个。

为什么这样要求？因为若是零点不唯一，就意味着零点存在定理的逆定理不一定成立。

函数零点存在定理的内容是：若函数 $f(x)$ 满足 $f(l)\times f(r)<0 \,\, (l<r)$，则 $f(x)$ 在 $(l,r)$ 上存在至少一个零点。

然而，如果用它来判定零点，我们需要用到其逆定理。不幸的是，在一般函数中，其逆定理并不成立，我们并不能说函数 $f(x)$ 不满足 $f(l)\times f(r)<0$ 时，$f(x)$ 在 $(l,r)$ 上一定不存在零点。

这时候硬套二分法会出现各种抽象的问题，比如：

有可能两边都有零点，那么哪边我们都不应该扔掉，否则会漏解，但两边都去也没法实现。
有可能两边都有零点，但两边各自用零点存在定理都判不出零点。

因此，我们必须限制函数的零点唯一，才能避免上面的所有问题。

三次函数的零点就不唯一，所以我们没法对整个答案范围跑一次二分求出所有的零点。

不过，由于题目中保证根之间的差大于1，也就是一个长度为1的区间中不存在两个以上的零点，于是我们可以把整个答案区间分成很多个长度为1的小区间，在这些小区间中进行实数二分即可。

写代码时依然要注意，$<0$ 不能直接写，要写 $<eps$。

三分

P3382 三分

此题的函数与前面的函数不太一样，它让我们求出函数的极值点，而不是求零点，所以普通的二分就不可用了。

当然，二分也不是完全不可用。比如这题，我们可以对给出的函数求导，这样极值点就转化为了导函数的零点。

这种方法的缺点也很明显，遇到一个非常抽象没法求导的函数你不炸了。

所以三分法就出现了，一个专门用于求解单峰函数极值点的方法。

首先，我们取 $[l,r]$ 之间的两个中间点 $lmid,rmid$，算出 $f(lmid),f(rmid)$ 的值，然后我们取更保守的那一个中间点更新区间。

什么叫“保守的”？以题目中给的左升右降的函数为例，如果 $f(lmid) \le f(rmid)$ 那么就让 $l \gets lmid$，否则 $r\gets rmid$。

每次都保守的选区间收缩比较小的方式，直到区间长度小于 $eps$ 为止。容易发现，这样取一定不会漏掉极值点，最后 $l$ 或 $r$ 就是极值点的横坐标。

在实现上，很多代码里都写 $lmid \gets l+\frac{r-l}{3},rmid\gets r-\frac{r-l}{3}$，也就是取两个三等分点。

但事实上，三分法的正确性并不取决于两个中间点的选取。

所以最好的方法，是取 $lmid \gets \frac{l+r}{2}-\Delta x,rmid \gets \frac{l+r}{2}+\Delta x$，也就是取中间点稍微偏一点点的两个点，这样的好处是更快，更接近 $\log_2$ 的复杂度。

通常情况下，$\Delta x$ 取 $\frac{eps}{3}$，这是为了避免死循环，如果 $\Delta x$ 大于 $\frac{eps}{2}$，那么在区间长度很接近 $eps$ 的时候，由于两个中间点的距离大于 $eps$，此时中间点跑到了区间的外面，就会导致死循环。

不难发现，这种方式相当于对中点取了个近似导数，所以也可以看做二分求极值。

点击查看代码

#include<bits/stdc++.h>
using namespace std;const int N=20;
const double eps=1e-6;
double a[N];
int n,m,ans;inline double f(double x){double now=1, ans=0;for(int i=0; i<=n; i++)ans+=now*a[i], now*=x;return ans;
}signed main(){cin.tie(0)->sync_with_stdio(0);double l,r;cin>>n>>l>>r;for(int i=n; i; i--) cin>>a[i];double lmid, rmid;while(l+eps<r){lmid=(l+r)/2-eps/3, rmid=(l+r)/2+eps/3;if(f(lmid)>f(rmid)) r=rmid;else l=lmid;}cout<<l;return 0;
}

三分法的局限性

同二分法一样，不是任何单峰函数的极值都可以用三分求。

这是因为如果单峰是不严格的，左侧和右侧的单调部分存在着相等的部分，那么如果找到一个 $f(lmid)=f(rmid)$，我们没法判断该怎么移动区间，三分法便不再适用。