二分法

luckydrawbox · 2022-02-21 17:08:10 · 个人记录

整数集合上的二分

假设函数 \text{check}(x)(x\in \mathbb{Z}) 满足存在一个整数 l，使得 [\forall i<l,check(i)=0]\land[\forall i\ge l,check(i)=1]。

• 求一个最小的 x，使 check(x)=1。

while(l<r)
{
    int mid=(l+r)>>1;
    if(check(mid))
        r=mid;
    else
        l=mid+1;
}

• 求一个最大的 x，使 check(x-1)=0。

while(l<r)
{
    int mid=(l+r+1)>>1;//必须+1
    if(check(mid))
        l=mid;
    else
        r=mid-1;
}

实数域上的二分

假设函数 \text{check}(x)(x\in \mathbb{R}) 满足存在一个实数 r，使得 [\forall i<r,check(i)=0]\land[\forall i\ge r,check(i)=1]。

接下来两个方法都是求上面的 r。

• 以精度 eps 为条件，一般需要保留 k 位小数时，取 eps=10^{-(k+2)}；表达式一般为 [l+eps<r]。

while(l+eps<r)
{
    double mid=(l+r)/2;
    if(check(mid))
        r=mid;
    else
        l=mid;
}

• 精度不适合表示或确定时，采用固定循环次数的二分方法,这种方法得到的结果的精度更高。

for(int i=1;i<=100;i++)
{
    double mid=(l+r)/2;
    if(check(mid))
        r=mid;
    else
        l=mid;
}