前置文章

二分查找

注意!!!!!!!!以下模板是闭区间内代码, 搜索结果是下标

模板1: 搜索左端点(小于等于x的值)

1
2
3
4
5
6
while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] >= x) r = mid;
            else l = mid + 1;
        }

模板2: 搜索右端点(大于等于x 的值)

1
2
3
4
5
6
while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (q[mid] <= x) l = mid;
                else r = mid - 1;
            }

搜索右端点时, 重点要寻找靠右的中点

一个mid = (l+r)>>1
一个mid = (l+r+1)>>1
加不加1 完全取决于 l = mid 还是r = mid
l等于mid时必须+1向上取整 不然会陷入l=l的死循环
r = mid 时候不用加1 因为下一步l = r 直接会退出循环

例如 在只有两个数的范围内搜索时, 而目标数又在左侧

1
2
3
[ 3 , 4 ]
target = 3
如果搜索靠左的数, 会无限制循环l = 3;

搜索失败的判定,

如果范围内找不到所要搜搜的值, 因为 l = mid + 1 会无限制的向边界搜索, 最后会返回边界, 也就是说会取得最接近答案的值.

所以二分是一定有答案的.且是最接近target的答案

小数二分模板

1
2
3
4
5
6
7
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;
    }

不区分左右边界问题

STL 库函数

lower_bound

upper_bound

默认二分函数寻找的是开区间,

lower_bound寻找不小于x 的数字, 而upper_bound 寻找第一个不符合x的数字

Lower_bound(begin(), end(), val, bool compare)

默认情况下: 在范围内找到一个不小于val的数

自定义情况: 根据 mycomp 规则，从容器中找到第一个违背 mycomp 规则的元素

upper_bound(begin(),end(), val, bool compare)

默认情况下: 在范围内找到一个大于val的数