我们都知道二分查找以及许多二分的应用。

但是二分主要是对于有单调性的函数或数列才能使用。

如果这个函数/数列没有单调性，而是有一种单峰/谷的特性。

我们可以使用三分法来确定这个函数的极值。

三分法的具体思想可在别处见到。

我就贴一个自己的模板，没有bug……

因为我曾经被一个有bug的模板坑害了……

速度非常快，常数应该很小。约是二分的两倍常数左右。

1 l=L,r=R;//确定l,r的初值,保证l<=r哦 2 while(l!=r){ 3     if(r-l<3){
   //[l,r]超过3就特判 4         Ans=Max4(Ans,f(i,l),f(i,l+1),f(i,r)); 5         break; 6     } 7     mid1=(l+r)/2, mid2=mid1+1;//将两点取得靠近中点，会减小常数 8     val1=f(i,mid1), val2=f(i,mid2); 9     if(val1>=val2) r=mid2;10     if(val1<=val2) l=mid1;11 }12 if(l==r) Ans=max(Ans,f(i,l));//对于开始时l==r的特判