二分问题总结

二分问题思想

二分问题的显著特点是某问题给定一个特定的值K，求关于K的一个参数值，若该参数对K的影响是单调的，那么便可以使用二分法来逼近K，以求得准确的参数。

种类

1.二分查找

给定一集合，查找是否存在某数。

//二分查找,传入初值[0,n-1]
int binarySearch(int A[],int left,int right,int x)
{
    int mid;
    while(left <= right)
    {
        mid = (left + right) / 2;
        if(mid > x)
            right = mid - 1;
        else if(mid < x)
            left = mid + 1;
        else return mid;
    }
    return -1;
}

2.二分查找第一个满足条件的某数

//传入[0,n]
int lowerBound(int A[],int left,int right,int x)
{
    int mid;
    while(left < right)
    {
        mid = (left + right) / 2;
        if(mid >= x)
            right = mid;
        else
            left = mid + 1;
    }
    return left;
}

3.二分查找最后一个满足条件的某数

可以转换为求解第一个不满足该条件的解，然后将该解的位置减一即可

4.二分求值

double f(double x) // 给定f二分求解f(x)=0的根
{
    return ...;
}

double solve(double L,double R,double eps) //eps:精度
{
    double left = L,right = R,mid;
    while(right - left > eps)
    {
        mid = (left + right) / 2;
        if(f(mid) > 0)
            right = mid;
        else
            left = mid
    }
    return mid;
}