icontofig | 发布于 2019-02-03 22:46:55 | 阅读量 426 | 三分
发布于 2019-02-03 22:46:55 | 三分

三分法

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

(图片转自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(厚脸皮)。


内容更新于: 2019-02-03 22:46:55
链接地址: http://blog.leanote.com/post/icontofig/d58a428997d2

上一篇: BUPT训练-Codefoces325E Red Button

下一篇: 数位DP & BZOJ1026[SCOI 2009]windy数题解

426 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航