二分

Published: September 12, 2019 by Daltao

• Categories:
• algorithm 101

• Tags:

• 三分算法
• 二分中的相对和绝对误差
• 缝隙二分

三分算法

假设存在一个定义域和值域均为$\mathbb{R}$的连续下凸函数$f$，要求求函数$f$的极小值。

一般的严格单调函数，我们可以利用二分查找法，以理论最优时间复杂度$O(\log_2D)$，其中D表示函数的定义域大小。

考虑到下凸函数的极值点左端为单调减函数，而右端为单调增函数。我们可以将二分转换为三分，即将区间$[l,r]$划分为$[l,ml]$,$[ml,mr]$和$[mr,r]$。其中$ml=l+(r-l)/3$，而$mr=r-(r-l)/3$。

我们考虑三种情况：

1. 极值点落在$[l,ml]$，这时候一定有$f(ml)\leq f(mr)$，我们可以重置$r=mr$。
2. 极值点落在$[mr,r]$，这时候一定有$f(ml)\geq f(mr)$，我们可以重置$l=ml$。
3. 极值点落在$[ml,mr]$，这时候我们可以任意选择重置$l=ml$或$r=mr$的一种。

换言之，我们可以总结为若$f(ml)\leq f(mr)$，则重置$r=mr$，否则重置$l=ml$。

由于每次减少$\frac{1}{3}$的区间，因此时间复杂度为$\log_{1.5}D$。

二分中的相对和绝对误差

现在很多输出浮点数的题目都会提供两种AC条件，一种是输出与真实结果的绝对误差不超过阈值，一种是输出与真实结果的相对误差不超过阈值。

绝对误差的定义为，预估值为$x$，真实值为$y$，那么绝对误差为$|x-y|$，同理相对误差可以定义为$|\frac{x-y}{y}|$。

之前一直都没太关注相对误差，但是最近在做Atcoder上的一道题的时候踩了坑。

相对误差在输出结果很大的时候会发挥巨大的作用。众所周知双精度浮点型共64位，其中1位用于表示符号，11位表示指数，其余的52位用于表示有效数字。简单换算就可以知道双精度浮点型可以精确表示大概15位十进制整数（$2^{10}\approx 10^3$）。

现在考虑一个问题，最终结果为$10^8$，但是要求绝对误差小于$10^{-8}$，这现实吗。事实上尾部的数值由于有效数值不足会被舍去。这就会导致二分的时候，$(l+r)/2$可能会等于$l$或等于$r$，从而导致二分进入死循环。

但是有了相对误差，情况就会大为不同，当输出为$10^8$时，我们可以不需要保留任意小数。

下面考虑相对误差为$t$时，二分左右边界为$l$和$r$时，如何判断是否达到了相对误差阈值，当$l<0<r$的时候，使用绝对误差进行测试，因为这时候不会出现精度问题。如果$l>0$，那么可以利用下面公式检测相对误差：

$$|\frac{y-l}{y}|\leq |\frac{r-l}{y}|\leq |\frac{r-l}{l}|\leq t\\$$

对应的，如果$r<0$，那么可以用下面公式检测相对误差：

$$|\frac{y-l}{y}|\leq |\frac{r-l}{y}|\leq |\frac{r-l}{r}|\leq t\\$$

缝隙二分

以前一直以为二分只能作用在单调函数上，现在发现二分还能作用在非单调函数上查找缝隙。

所谓的缝隙是指这样一个整数$x$，满足$check(x-1)\neq check(x)$。

要执行缝隙二分的前提是，一开始给定的$l$和$r$满足$check(l)\neq check(r)$。

在执行缝隙而二分的过程，利用$l$和$r$算出$mid=(l+r)/2$后，如果$check(mid)=check(l)$，那么就令$l=mid$，否则令$r=mid$。容易发现这样做始终能保证$check(l)\neq check(r)$。由于区间在不断缩小，因此最终一定能找到一个缝隙。当然我们无法确定找到的是哪个缝隙，但是这不重要。

可以试试Atcoder的这道题目，它就利用了缝隙二分的方法。