三分

约 123 个字 25 行代码 预计阅读时间 1 分钟

三分

求单峰函数的极大值

单峰函数：先单调增再单调减的函数

设该函数为 $f$，比较相邻点的值大小关系，如果左点大于右点，答案在右点左边，反之在左点右边

对于整数和实数的边界处理不一样

//整数
while(l<=r)
{
    mid=(l+r)/2;
    if(check(mid)<check(mid+1))
    {
        l=mid+1;
        ans=mid;
    }
    else
        r=mid-1;
}

//实数
int times=100;
while(times--)
{
    mid=(l+r)/2;
    if(check(mid)<check(mid+eps))
    {
        l=mid;
        ans=mid;
    }
    else
        r=mid;
}

对于二元函数，如果固定一元，另一元都是单峰函数，可以三分套三分，当然，可以进一步推广到更多元函数