三分法的适用范围

三分法是一种常用的求凸函数最值的方法。它的实现和二分法没什么区别。

while(l < r){
    int mid = (l + r) >> 1;
    if(check(mid) < check(mid + 1)) r = mid;
    else l = mid + 1;
}

有的人把上面的过程称做是在二分斜率。这在某种意义上是正确的，不过它不是在二分斜率的大小，而是在二分斜率的正负性。

如果不考虑斜率为 $0$ 的情况，单峰函数斜率的正负性也是单调的。因此纵使一个单峰函数不具有凸性，只要其不存在斜率为 $0$ 的线段 ($f(i)\neq f(i+1)$)，同样可以使用三分法求最值。凸函数存在斜率为 $0$ 的线段是不影响正确性的，因为凸函数只有最值点的斜率可能为 $0$。

如果单峰函数存在斜率为 $0$ 的段，可以尝试使用以下的玄学代码骗分：

while(r - l > 10){
    int m1 = l + (r - l + 1) / 3, m2 = r - (r - l + 1) / 3;
    if(check(m1) < check(m2)) r = m2 - 1;
    else l = m1;
}

其“原理”是，一般来说，长长的一段的斜率更不容易为 $0$。

评论