算法浅谈——二分法的进阶版，三分算法

本文始发于个人公众号：TechFlow

之前的文章当中我们详细阐述了二分法，尤其是讨论了我们在编写代码时候的边界问题。传送门：

今天这一篇文章，我们继续来讲算法，我们不讲二分法了。来讲讲二分法的进阶版——三分法。

是的，你们没有看错，这不是我任性起的名字，而是实实在在的有这个算法。不过如果去搜索引擎里搜，大概率会搜到摄影的三分构图法，而很难搜索三分查找的算法。

主要原因是它和二分法比较起来要小众得多，几乎所有的算法书籍当中都没有三分法的介绍。它更多的是存在于ACM-ICPC这类算法竞赛当中，不过小众没关系，只要有用就好。三分法的原理也很简单，和二分法几乎一模一样，只不过我们分隔区间的时候，不是将区间一分为二，而是一分为三。之后，我们同样通过缩小区间的方法来确定要查找的值所在。

看到这里，我相信你们应该都能理解算法原理，但是肯定会有一个问题要问：既然分成两份就能解决问题，我们为什么要分成三份呢？

在回答这个问题之前，我们先来看另一个问题。在数学上，二分法究竟解决了一个什么问题？

还记得二分法使用的前提么？数组必须是有序的，所以二分法其实解决的是单调函数的求解的问题。只要数组是有序的，根据函数的定义就可以看做是一个将数组下标映射到数组取值的函数。显然，这是一个单调函数。我们通过二分法查找其中的一个元素v，本质其实是查找 f(x) = v
这个函数的解。

所以，二分法使用的场景是单调函数，也就是一次函数。那如果我要搜索二次函数的最小值，用二分法可行吗？

图片说明

显然不可行，因为我们在取完mid之后，并不知道答案可能出现在左右哪个区间。
这个时候就需要三分法出场了。

图片说明

三分***将区间分成三份，这个我们都已经知道了。分成三份，自然需要两个端点。这两个端点各有一个值，我们分别叫做m1和m2。我们要求的是函数的最小值，所以我们要想极值逼近。

但是我们有两个中间点，该怎么逼近呢？

我们直接根据函数图像来分析，根据上图我们可以看出来，m1和m2的函数值和它们距离极值点的远近是有关系的。离极值点越近，函数值越小(也有可能越大，视函数而定)。在上图当中，

，所以m2离极值点更近。我们要缩小区间范围，逼近极值点，所以我们应该让l=m1

图片说明

这里有一点小问题，我们怎么确定极值点在m2和m1中间呢？万一在m2的右侧该怎么办呢？

我们画出图像来看，这种情况其实并没有区别，我们只会抛弃区间[l, m1]
，并不会影响极值点。

会不会极值点在m1左侧呢？这是不可能的，因为如果极值点在m1左侧，那么m2距离极值点一定比m1远，这种情况下m2处的函数值是不可能小于m1的。

也就是说，三分法的精髓在于，每次通过比较两个值的大小，缩小三分之一的区间。直到最后区间的范围小于我们设定的阈值为止。算法并不难理解，但是当我们真正碰到二次函数的极值问题的时候，如果没有事先接触过三分法，很难一下想到算法。

三分法本身并不难，我们理解了算法之后，写出伪代码来就很容易了：

def trichotomy():
    l, r = start, end
    epsilon = 1e-6
    # 我们自定义的终止条件是区间长度小于1d-6
    while l + epsilon < r:
        margin = (r - l) / 3.0
        m1 = l + margin
        m2 = m1 + margin
        if f(m1) <= f(m2):
            r = m2
        else:
            l = m1
    return l

最后，我们看一道三分法相关的算法题，来实际演练一下三分法吧。

这是一道POJ3737，链接如下：http://poj.org/problem?id=3737

我来简单介绍一下题意。题意很简单，当下我们拥有一块布，我们知道布的大小，要将布做成一个圆锥形。要使得圆锥形的体积最大，假设布在加工的过程当中没有损耗，请问这个圆锥的体积、底面半径和高分别是多少？

我这里先不放答案，大家不妨自己想一下，实在做不出来，在公众号内回复三分法答案，获取题解。

如果觉得文章有所帮助，请扫码给个关注吧：

图片说明