之前介绍了二分搜索查找算法，它是用来查找满足单调的序列的元素值。
本文来介绍三分搜索查找算法，它是用来求给定自变量范围的凸函数或凹函数的最值问题，以凸函数为例，图像如下
如何通过三分方法来求它的极值？ 当然这个函数比较简单，直接配方法就知道结果了，但通常情况下我们知道了一定范围内自变量的目标函数是凸函数，但通过初等的方法很难求出极值，那么这时候三分搜索算法就派上用场了，后面会有具体的例子。
三分查找搜索算法原理
三分搜索算法将区间自变量的区间分为相同的三等分，那么这个区间中还有两个点，如下图
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了。
文章最后
怎么快速学C/C++，有什么方法，打算深入了解这个行业的朋友，可以加C/C++学习群：648778840，不管你是小白还是大牛，小编我都欢迎，不定期分享干货，包括小编自己整理的一份2019最新的C/C++资料和0基础入门教程，欢迎初学和进阶中的小伙伴。
每天晚上20:00我都会开直播给大家分享C/C++编程学习知识和路线方法，群里会不定期更新最新的教程和学习方法，大家都是学习C/C++的，或是转行，或是大学生，还有工作中想提升自己能力的前端党，如果你是正在学习C/C++的小伙伴可以加入学习。最后祝所有程序员都能够走上人生巅峰，让代码将梦想照进现实，非常适合新手学习，有不懂的问题可以随时问我，工作不忙的时候希望可以给大家解惑。
网友评论