想必大家不会陌生,二分查找,又名折半查找。是一种非常经典,简单又实用的查找算法。而在二分的基础行又衍生出了三分查找的技术和应用。
三分查找
三分查找的思路与二分查找非常类似。从字面意思可知二分查找是把数据分成两份,而三分是把数据分为三份。
适用场景
三分法可以帮助我们求出单峰函数的极值点(单峰函数的极值就是最值),有 凸曲线 和 凹曲线 两种类型。
通过将不断舍去三份区间的其中一份,不断逼近整体的峰值点。
实例分析:
本题不是裸的三份查找,因此先进行简单的分析。
这正好符合凹曲线的性质。我们可以绘制出下图的模型。