之前介绍了二分搜索查找算法，它是用来查找满足单调的序列的元素值。

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

写这篇文章之前，想说一句有想要学习c/c++的同学话，关注小编头条号，私信【编程】即可免费领取本文一整套系统的c/c++学习教程。

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

三分查找搜索算法原理

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

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了。

获取方式：

1.在你手机的右上角有【关注】选项，或点击我的头像，点击关注！（关注我）

2.关注后，手机客户端点击我的主页面，右上角有私信，请私信发我：编程

电脑已经设置好了关键词自动回复，自动领取就好了！这几天上万个消息，真的回复不过来，所以回复的时候请注意关键词！

其实做为一个开发者，有一个学习的氛围跟一个交流圈子特别重要这里请私信我“编程”不管你是小白还是大牛欢迎入住大家一起交流成长。小编会在里面不定期分享干货源码，包括我精心整理的一份c++零基础教程。欢迎各位感兴趣的的小伙伴。

学习思路：

学习资料：