三分法

解释

三分法,顾名思义,通过不断将一串数分为三段后精确范围.

相比于二分法,三分法还能实现对只有一个峰顶的函数的查找,如二次函数.而二分法只能查找单调递增的函数

实现方法

(与二分相似)

设左右端点为l和r,则找两个点(m1=(l+r)/2,m2=(l+r)/4+m1),根据m1,m2的大小来判断峰顶可能的范围,并从而起到精确的作用.

一般情况下,可以确定一个三分法次数,例如50,因为一般这样三分后,进度足够(二分也一样)

以下两种特殊情况用三分法无法精确得求出,故应特殊处理:

对于整数的三分,当l-r较小时,即可停止三分,进行暴力枚举,找到峰顶

对于分段函数,先当作浮点数处理,找到后,再起左右各枚举n个数,n据时间复杂度来定,一般可以为100000.