絮絮叨叨
相信站内的大家一定都是老基础人了。记得y总说过,基础课虽然每个知识点的难度不大,但是这些知识点都是前人潜心研究多年的智慧结晶。处于小白阶段的我们如果想吸收一个结晶没问题,但是一次性吸收一堆结晶难度就有些大了。
在这里我认为二分就是一个比较难以吸收的知识(基于自己的经验,都是泪……),尤其是当y总在基础课的 AcWing 789. 数的范围 上华丽地写出两套模板,当时看课的我立马暂停视频,火速把代码抄下来,但当我将l + r >> 1
和l + r + 1 >> 1
对应的代码交换时,我呆了,为什么会报错,不是y总说,+ 1
的区别仅仅在所查找的值与mid的关系吗,那按道理来说应该不会错的呀……
经过了n遍二分题目的默写和看y总语法基础课里介绍lower_bound()
以及upper_bound()
的时候,我恍然大悟,终于明白了+ 1
的区别不只有为了避免死循环,更重要的是它们两个是完全不同的方法,就如同lower_bound()
和upper_bound()
的区别。为了总结一下自己的思考结果,同时给在学习二分时同样有上述困惑的小伙伴们提供一个思路,就有了这篇分享。如果有哪里理解不到位,还请在评论区批评指正~
正文
首先我们来看下y总的二分查找模板
const int N = 1e6 + 10;
int a[N];
//不 + 1 版本
int l = 0, r = N - 1;
while(l < r)
{
int mid = l + r >> 1;
if (a[x] <= a[mid]) r = mid;
else l = mid + 1;
}
由于默认大家已经看过y总的基础课了,上面不 + 1 版本的代码含义就不再赘述。这篇代码如果要理解,我认为最核心的部分就是这个r = mid
。因为它代表着如果目标值小于当前_区间中点_的值,那么我的区间右端点就要移动到区间中点以便下一次查找时缩短区间。也就是,当区间右端点在向中间移动的时候,查找区间在不断_往左移动_,最终锁定到了等于目标值的第一个点,也就是题目当中的第一个相同元素的位置,也即lower_bound()
的含义,返回等于对应元素值的第一个位置。
同样就有
const int N = 1e6 + 10;
int a[N];
//+ 1 版本
int l = 0, r = N - 1;
while(l < r)
{
int mid = l + r + 1>> 1;
if (a[x] >= a[mid]) l = mid;
else r = mid - 1;
}
这段+ 1版本的代码说的是,如果目标值大于当前_区间中点_的值,那么我的区间左端点就要移动到区间中点以便下一次查找时缩短区间,也就是将查找区间不断_向右移动_,也就是upper_bound()
的含义。当然,这里为了防止死循环,在mid取值时就是要多 + 1,而这反倒也为我们记忆和区别这两种方法做了相应提示(if
当中对区间左右端点的移动也是标志,但我觉得不如将这两种方式通过+ 1区别开来记忆来的清楚)
想明白这点之后,对于lower_bound()
以及upper_bound()
的使用也变得丝滑起来了。如果只是找单一的点的位置,那么这两种方法其实都一样。但是一旦像上面那道题里,要输出第一个位置和最后一个位置的时候,那就需要搞搞清楚这两种模板之间到底有什么样的差异了。
本来还想详细讲讲区间端点取值,画几张图什么的,但是一敲字就懒起来了(突然感觉读字的话也是比较清楚的哈哈)
第一次写博文,各位大佬如果拍,请轻拍……
其实就是代码的整除是向下取整,所以到达临界条件时候的l与r,看是取l 还是 r ,l 的话就是向下取整 ,r 的话就要向上取整,向上取整就要+1