参考博客：https://blog.csdn.net/beiyouyu/article/details/7875480

概念

在二分查找的基础上，在右区间（或左区间）再进行一次二分，这样的查找算法称为三分查找，也就是三分法。

三分查找通常用来迅速确定最值。

三分法所面向的搜索序列的要求是：序列为一个凸性函数。通俗来讲，就是该序列必须有一个最大值（或最小值），在最大值（最小值）的左侧序列，必须满足不严格单调递增（递减），右侧序列必须满足不严格单调递减（递增）。如下图，表示一个有最大值的凸性函数：

算法过程

1⃣️先取整个区间的中间值mid。

int mid=(l+r)>>1;

2⃣️再取右侧区间的中间值rmid，从而把区间分为三个小区间。

int rmid=(mid+r)>>1;

3⃣️比较mid与rmid谁最靠近最值，只需要确定mid所在的函数值与rmid所在的函数值的大小。当最值为最小值时，mid与rmid中较小的那个自然更为靠近最值。最值为最大值时同理。

ll t1=Calc(mid),t2=Calc(rmid);//若求最大值则<,min取max
if(t1>t2) l=mid;
else r=rmid;
ans=min(ans,min(t1,t2));

模板

感谢学长的模板orz

ll Calc(ll x)//取最小值
{
}
ll Tsearch(int l,int r)
{
    ll ans=min(Calc(l),Calc(r));
    while(l<r)
    {
        int mid=l+r>>1;
        int rmid=mid+r>>1;
        ll t1=Calc(mid),t2=Calc(rmid);
        if(t1>t2) l=mid;//若求最大值则<,min取max
        else r=rmid;
        ans=min(ans,min(t1,t2));
    }
    return ans;
}