三分法

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

三分法

我们已经学过有序序列查找元素的二分法了,那么这次来学一下三分法。
三分法,故名思义,就是把一个区间分成三份。
但是这三分法是用来干什么的呢?
三分法是用来求解单峰函数型(凸型序列,包括上凸和下凸)查找元素问题最值的有力手段。

(图片转自chenxiaoran666的博客)

三分的核心思路如下: 对于当前的区间[l,r],求出midl = (l+r)/2,midr = (midl+r)/2,比较f(midl)与f(midr)的值哪个更接近于最值,并根据结果确认下一个搜索区间是[l,midr]还是[midl,r],直到l>=r。


示例代码

我们以上凸序列为例

int find(int l,int r){
    if(l >= r)return l;
    int midl = (l+r) >> 1;
    int midr = (midl + r) >> 1;
    if(a[midl] > a[midr])
        return find(l,midr);
    else return find(midl,r);
}​

当然也是可以写成迭代形式的,如下:

while(l < r){
    int midl = (l + r) >> 1;
    int midr = (midl + r) >> 1;
    if(a[midl] > a[midr])
        r = midr;
    else l = midl;
}​

虽然很少用,但是这种方法还是会有些用的,例如凸包。

如果各位官爷学到的话,请在我的QQ点个赞吧,QQ932901730(厚脸皮)。

Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00