三分查找

三分查找用于求单峰函数的极值。
速度快，但是结果并非准确值。

方法

首先，在函数上标4个点：$x=le,rt,mid,mmid$。其中$mmid$是$mid$与$rt$的中点。

现在的任务是通过迭代缩小范围：

1. 如果$f\left(mid\right)>f\left(mmid\right)$，则$mmid$一定在峰的右边。
2. 如果$f\left(mid\right)<f\left(mmid\right)$，则$mid$一定在峰的左边。

证明： 1. 我们假设存在$f\left(mid\right)>f\left(mmid\right)$且$mmid$在峰的左边。
由于$f\left(x\right)$在峰的左边单调递增，且$f\left(mid\right)>f\left(mmid\right)$，所以$mid$在$mmid$的右边。
然而$mmid=\frac{mid+rt}{2}$，显然$mid$在$mmid$左边。矛盾。

2. 我们假设存在$f\left(mid\right)<f\left(mmid\right)$且$mid$在峰的右边。
由于$f\left(x\right)$在峰的右边单调递减，且$f\left(mid\right)<f\left(mmid\right)$，所以$mid$在$mmid$的右边。
然而$mmid=\frac{mid+rt}{2}$，显然$mid$在$mmid$左边。矛盾。

食用姿势

首先我们要证明，需要三分的函数是个单峰函数。
然后就可以写三分了。

如何控制精度？
两种办法。一种是控制迭代次数，一种是直接控制精度。

控制迭代次数：设一个$lambda$值，迭代了这么多次之后就退出。
直接控制精度：设一个精度限制$eps$，如果$rt-le<eps$就退出。

具体用哪种方式由题目决定。
一般来说，如果题目要求控制相对精度，控制迭代次数比较好；如果题目要求控制绝对精度，直接去控制精确到小数点后多少位比较好。