三分查找
三分查找用于求单峰函数的极值。
速度快，但是结果并非准确值。
方法
首先，在函数上标4个点：x=le,rt,mid,mmid。其中mmid是mid与rt的中点。
现在的任务是通过迭代缩小范围：
- 如果f(mid)>f(mmid)，则mmid一定在峰的右边。
- 如果f(mid)<f(mmid)，则mid一定在峰的左边。
证明：
- 我们假设存在f(mid)>f(mmid)且mmid在峰的左边。
由于f(x)在峰的左边单调递增，且f(mid)>f(mmid)，所以mid在mmid的右边。
然而mmid = \frac{mid+rt}{2}，显然mid在mmid左边。矛盾。 - 我们假设存在f(mid)<f(mmid)且mid在峰的右边。
由于f(x)在峰的右边单调递减，且f(mid)<f(mmid)，所以mid在mmid的右边。
然而mmid = \frac{mid+rt}{2}，显然mid在mmid左边。矛盾。
食用姿势
首先我们要证明，需要三分的函数是个单峰函数。
然后就可以写三分了。
如何控制精度？
两种办法。一种是控制迭代次数，一种是直接控制精度。
控制迭代次数：设一个 lambda 值，迭代了这么多次之后就退出。直接控制精度：设一个精度限制 eps ，如果 rt-le < eps 就退出。
具体用哪种方式由题目决定。
一般来说，如果题目要求控制相对精度，控制迭代次数比较好；如果题目要求控制绝对精度，直接去控制精确到小数点后多少位比较好。
-------------本文结束感谢您的阅读-------------
本文作者： jfy
本文链接： http://example.com/2019/10/16/%E4%B8%89%E5%88%86%E6%9F%A5%E6%89%BE/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
