随笔分类
二分
整数二分
有 单调性肯定可以进行二分,但是可以进行二分的不一定是有单调性的
二分本质上就是可以通过定义一个 性质(二段性),将一个区间划分为两个不相交的子区间,右边的区间满足性质,左边的区间不满足性质.
- 此时通过二分便能够找到左区间的右边界,或是右区间的左边界.
- 即通过二分把性质的边界给二分出来
二分的模板一共有两个,分别适用于不同情况
算法思路:假设目标值在闭区间 [ l, r ],每次将区间长度缩小一半,当 l = r 时,我们就找到了目标值 -> 每一次二分都能确定答案是在区间里.
① 左区间的右边界
int l = 0, r = len - 1;
while (l < r) {
int mid = l + r + 1 >> 1; // 这里的 + 1是为了防止数组中只有两个数时,且第一次判断为 true下,l、r都没有发生变化造成的死循环的问题.
if (check(mid)) l = mid;
else r = mid - 1;
}
// 判断
② 右区间的左边界
int l = 0, r = len - 1;
while (l < r) {
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
核心思想:二分时不用判断有没有解的情况,二分是基于有解的情况来进行划分的,根据划分出来的边界 l、r来判断数组中有没有解.
二分不用死记硬背,先背模板,根据条件以及根据条件所做的操作来判断 mid需不需要进行 + 1即可.
浮点数二分
例如:求一个数的三次方根
同样可以利用二分思想,但需要保证 r > 1,且因为是浮点数,在更新时 l并非是 + 1操作的.