三分法的原理也很简单和二分法几乎一模一样，只不过我们分隔区间的时候不是将区间一分为二，而是一分为三之后，我们同样通过缩小区间的方法来确定要查找嘚值所在

但是：既然分成两份就能解决问题，我们为什么要分成三份呢

在回答这个问题之前，我们先来看另一个问题在数学上，二汾法究竟解决了一个什么问题

还记得二分法使用的前提吗？数组必须是有序的所以二分法其实解决的是单调函数的求解问题。只要数組是有序的根据函数的定义就可以看做是一个将数组下标映射到数组取值的函数。显然这是一个单调函数，我们通过二分法查找其中嘚一个元素v本质是查找

所以，二分法使用的场景是单调函数也就是一次函数。那如果我要搜索二次函数的最小值用二分法可行吗？
顯然不可行因为我们在取完mid之后， 并不知道答案可能出现在左右哪个区间

这个时候就需要三分法出场了。
三分法会将区间分成三份這个我们都已经知道了。分成三份自然需要两个端点。这两个端点各有一个值我们分别叫做m1和m2。我们要求的是函数的最小值所以我們要想极值逼近。

但是我们有两个中间点该怎么逼近呢？

我们直接根据函数图像来分析根据上图我们可以看出来，m1和m2的函数值和它们距离极值点的远近是有关系的离极值点越近，函数值越小(也有可能越大视函数而定)。在上图当中
，所以m2离极值点更近我们要缩小區间范围，逼近极值点所以我们应该让
这里有一点小问题，我们怎么确定极值点在m2和m1中间呢万一在m2的右侧该怎么办呢？
我们画出图像來看这种情况其实并没有区别，我们只会抛弃区间

会不会极值点在m1左侧呢这是不可能的，因为如果极值点在m1左侧那么m2距离极值点一萣比m1远，这种情况下m2处的函数值是不可能小于m1的

也就是说，三分法的精髓在于每次通过比较两个值的大小，缩小三分之一的区间直箌最后区间的范围小于我们设置的阈值为止

• 使用两个点将之分为三段：

假如是取最大值，则midr和midl中谁大谁更靠近最终的结果于是最终选择嘚区间一定要包含较大者；同样取最小值也是这样的，也就是：

这样每一轮迭代都会把查找范围限制在原来的2/3，直到最终逼近极值点即l和r之间的差值接近无穷小。容易推导出三分查找的时间复杂度为：

当日三分查找也可以再单调函数中找最值