[算法总结] 二分

二分

• 说在前头:
• 整数二分
• 实数二分
• 二分的应用

说在前头:

对二分理解:

普通二分
就是在一个有序的序列里面
通过不断二分区间来寻找答案

进阶二分
就是将问题的答案区间抽象成

答案成立 和 答案不成立的 两个区间

然后通过不断缩小区间来查找答案

整数二分

注意

控制范围(什么时候+1,这个是较为重要的)

Code:

找第一个小于x的数

while(l<r)
{
    int mid = l+r>>1;
    if(a[mid]>=x) r= mid;
    else l = mid+1;
}

找第一个大于x的数

while(l+1<r)
{

    int mid = l+r>>1;
    if(a[mid]<=x) l=mid;
    else r= mid;
}

lower||upper_bound

返回数组中第一个大于或等于被查数的值

int pos1=lower_bound(num,num+6,7)-num;    

返回数组中第一个大于被查数的值

 int pos2=upper_bound(num,num+6,7)-num; 

切换成小于

int pos3=lower_bound(num,num+6,7,greater<int>())-num;  
int pos4=upper_bound(num,num+6,7,greater<int>())-num; 

实数二分

区别

拿数的三次方根为例

因为是实数,mid取的也是小数

所以们需要改一下while和mid即可

code:

int main()
{
    double x;
    cin >> x;

    double l = -100, r = 100;
    while (r - l > 1e-8)
    {
        double mid = (l + r) / 2;
        if (mid * mid * mid >= x) r = mid;
        else l = mid;
    }
    printf("%.6lf\n", l);
    return 0;
}

二分的应用