二分法和三分法的理解,心理学三分法和二分法

三分法介绍

在区间内用两个mid将区间分成三份，这样的查找算法称为三分查找，也就是三分法，三分法常用于求解单峰函数的最值。

还有一种理解，即在二分查找的基础上，在左区间或者右区间上再进行一次二分。

三分与二分的区别

二分法适用于单调函数，而单峰函数用二分明显不太好了，对于有些单峰函数，可以求导后转化为单调函数，从而使用二分，然而很多情况求导是很麻烦的，这时就需要用到三分了。

算法介绍

1.先将区间三分，每个区间的长度为1/3(right-left)

mid1=left(right-left )/3； mid2=right-(right-left )/3；

2.比较mid1和mid2谁更靠近极值，如果mid1更靠近极值，右区间改为mid2,否则左区间改为mid1(后面的代码都是 以求最大值为例）

if(calc(mid1) calc (mid2) ) left=mid1； elseright=mid2；

重复1、2的过程，直到不满足left epsright，也就是找到最高值为止

算法模板

#define eps 10e-6double cal (() ) /计算主题所需的值while (le PSR ) ) m1=L(R-L )/3； M2=R-(R-L )/3； v1=cal(m1； V2=cal(M2 )； if(V1V2 ) l=m1； else r=m2； }

另一种写法

doublecalc(typea )/*从主题的意义看(/) void solve (void ) ) { double Left，Right； double mid，midmid； double mid_value，midmid_value； Left=MIN； Right=MAX； wile(leftEPSright ) mid=) leftright )/2； midmid=(midright )/2； mid_area=calc(mid； midmid_Area=calc(midmid )； if(mid_area=midmid_area ) Right=midmid； else Left=mid； }

我个人还是喜欢第一种写法。 感觉区间的大小一样，或者稍微协调一点的o(_) O~~。

几道题目三分题

poj 3737UmBasketella