[算法总结] 二分

说在前头: 对二分理解:

普通二分 就是在一个有序的序列里面 通过不断二分区间来寻找答案 进阶二分 就是将问题的答案区间抽象成 答案成立 和 答案不成立的 两个区间 然后通过不断缩小区间来查找答案

整数二分

注意

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

Code: 找第一个小于x的数

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

找第一个大于x的数

while(l+1>1;
    if(a[mid]> 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;
}

二分的应用