上一篇文章介绍了二分搜索查找算法，它是用来查找满足单调的序列的元素值。

本文来介绍三分搜索查找算法，它是用来求给定自变量范围的凸函数或凹函数的最值问题，以凸函数为例，图像如下

如何通过三分方法来求它的极值？ 当然这个函数比较简单，直接配方法就知道结果了，但通常情况下我们知道了一定范围内自变量的目标函数是凸函数，但通过初等的方法很难求出极值，那么这时候三分搜索算法就派上用场了，后面会有具体的例子。

三分查找搜索算法原理

三分搜索算法将区间自变量的区间分为相同的三等分，那么这个区间中还有两个点，如下图

c、d两个点将区间[a, b]划分为长度相等的三段，其中c点和d点的横坐标分别如下

如果c比d更靠近顶点最值，那么舍弃右区间，否则舍弃左区间，这样迭代下去就能找到最值了。为什么这样做就能求到最终的最值呢？ 下面证明一下

1. 如果c点和d点在最值的同一侧，由于凸函数在最值得任何一侧都具有单调性，那么无论是在左侧还是在右侧，都只需要保留离最值最近的点就可以了

2. 如果c点和d点在最值的两侧，那么如上图，舍弃掉[a, c]区间后并不影响求最值

那么根据这个原理，三分搜索的代码如下

double ternary_search(double a, double b) { while(b - a > 1e-4) { double c = (2 * a + b) / 3; double d = (a + 2 * b) / 3; double fc = fun(c); double fd = fun(d); if(fc > fd) { a = c; } else { b = d; } } return a;}

其中fun(x)为满足条件的凸函数。

三分搜索查找算法的应用

接下来看几道题，关于三分搜索查找算法的应用。

1. 给定一个直角弯道的两条道路的宽度x和y，然后再给出汽车的长度l与宽度w，问汽车能否通过该弯道，如下图。

若汽车的左边贴着上面的直角边，同时汽车的右下角紧贴着下面的线，这是最优的方案。若这样都过不了，其它方式也无法通过该弯道，我们只需要求汽车右上角的点P的会不会碰到最右边，如果碰到则无法通过，否则能通过。

针对上图，以O点建立直角坐标系，那么P点的横坐标关于α的函数可以表示如下

很明显在车过弯道过程中，P的横坐标值是先增大后减小，是一个凸函数。那么通过三分方法求f(α)的最大值是否大于y，如果大于y则不能通过，否则能通过。

2. 在一个平面坐标系中给定n个点，其中n小于100000，在x轴上找一点，使得这个点到所有点的距离之和最短。

设x轴上要找的点为(x, 0)，距离和的函数为f(x)，那么得到

对其求二阶导数，得到

所以f(x)是一个凸函数，那么就可以用三分搜索算法求出x了。