这两天在刷二分的题,因为当初没学好,被搞得很难受,经过这几天多次思考,多道题目的折磨,坐牢了几个下午,稍微悟了一小点,分享一下!!
本文提示:本文不做详细证明,如果想看证明可以看点赞第一的那位大佬的文章(实在没那能力)
y总的模板
只是修改名称 为了好记住而已和y总的一样
最后return
的时候 l和r都是可以 因为最后一定r==l
(二分终止条件)
//查找左边界 SearchLeft 简写SL
int SL(int l, int r)
{
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
return l;
}
//查找右边界 SearchRight 简写SR
int SR(int l, int r)
{
while (l < r)
{
int mid = l + r + 1 >> 1; //需要+1 防止死循环
if (check(mid)) l = mid;
else r = mid - 1;
}
return r;
}
记忆方面:
来自视频评论区下方的一句话 : 有加必有减
int mid = l + r + 1 (加)>> 1;
if (check(mid)) l = mid;
else r = mid - 1 (减);
图解
左边界 :边界最左边的那个数 右边界同理。
一般二分应用于无非下面这四种情况:
1:找大于等于数的第一个位置 (满足某个条件的第一个数)
2:找小于等于数的最后一个数 (满足某个条件的最后一个数)
3.查找最大值 (满足该边界的右边界)、
4.查找最小值 (满足该边界的左边界)
这里图片不知道为什么 现在看不了了 可以看下面链接
可以用SL() 和 SR() 模板 分别查找同一个重复数字, 你就会发现返回的下标不是同一个值。
然后每次使用这这两个模板的时候,先想是找这个区间的左端点还是还是右端点,然后选择用模板,最后再去写判断条件。如果你是新手,模板题做完,可以去找几道同类型算法题练练巩固下
推荐习题: 四平方和 分巧克力 机器人跳跃问题 , AcWing 1236. 递增三元组
下面这俩道是洛谷, 应用的3 和4 查找最值
https://www.acwing.com/blog/content/21312/
https://www.acwing.com/solution/content/118815/
下面是这道题的代码
C++代码
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N];
int SL(int l, int r, int x) {
while (l < r) {
int mid = l + r >> 1;
if (q[mid] >= x) r = mid;
else l = mid + 1 ;
}
return l;
}
int SR (int l, int r, int x) {
while (l < r) {
int mid = l + r + 1 >> 1;
if(q[mid] <= x) l = mid;
else r = mid - 1;
}
return r;
}
int main() { int n,m;
scanf ("%d%d",&n,&m);
for(int i=0;i<n;++i) scanf ("%d",&q[i]);
while ( m-- ) {
int x;
scanf ("%d",&x);
int l = SL(0, n - 1, x);//查找左边界 并返回下标l
if (q[l]!=x) cout <<"-1 -1"<<endl;//如果找不到 返回-1 -1
else {
cout << l << ' '; //如果找到了 输出左下标
cout << SR(0, n - 1, x) << endl; //输出右下标
}
}
return 0;
}
leetcode 题 可以写一下 我的写法是找左右边界
题目链接
class Solution {
public:
// 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
int findRepeatNumber(vector<int>& nums) {
int len = nums.size();
sort(nums.begin(), nums.end());
for(int i = 0; i < len ; i ++) {
int x = nums[i], l =0, r = len - 1;
while(l < r) {
int mid = l + r >> 1;
if(nums[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
int L = l;
l = 0, r = len - 1;
while(l < r) {
int mid = l + r + 1 >> 1;
if(nums[mid] <= x) {
l = mid ;
} else {
r = mid - 1;
}
}
int R = r;
if(L != R) {
return x;
}
}
return 0;
}
};
最后一题 究极二分
https://www.acwing.com/solution/content/120802/
可以,最简洁的解释了。起名SL和SR确实容易记忆。
哥们,头像把我逗笑了
😍
小口诀!
男左女右 (判断为true时) 男是一 所以加一 女是零所以不用加
左加右减 (判断分界点时且不满足时)比如判断右边界点时
不满足条件时,右边界点此时不在mid所在的左区域中,至少加1,即 l = mid + 1
关键是check(mid)你怎么分析出来的??都没分析直接上答案?
题目都不一样,我怎么分析 ,难不成每个题的check条件都一样吗?
右加必有右减
右加必有减
可不可以只求左端点,然后从左端点向右遍历找到右端点
int key;
scanf(“%d”, &key);
int first = lower_bound(a, a + n, key) - a;
if(first != n)
{
if(a[first] == key)
{
int end = first;
while(a[end+1] == key)
{
end ++;
}
cout<<first<<” “<<end<<endl;
}
else cout<<-1<<” “<<-1<<endl;
}
else
{
cout<<”-1”<<” “<<”-1”<<endl;
}
怎么求右端点?你得考虑还有不重复的情况, 时间复杂度就不是O(logn)了 会到O(n)
明白了!!
请宁证明一下,如果是单调递减,你所谓的结论是否仍然成立
证明在这 链接
我问的是数组元素单调递减,不是单调增。ok?
有意义吗? 你递减你就改个判断不就可以?
可以将递减的reverse
之后再去找就好了
牛啊,豁然开朗
还得是你
注意:左右边界通过下标区分
[HTML_REMOVED]
check是啥至今都不知道
写的很好,但是这种比较复杂的边界条件我还是很难理解
只能硬记了
我想知道m起着一个什么作用啊。
直接悟了,之前一直不明白什么时候用sl sr
请问一下,怎么确定check()
左边界是>=,右边界是<=
牛哇牛哇
请问博主:1.找大于等于数的第一个位置 (满足某个条件的第一个数)和4.查找最小值 (满足该边界的左边界)有什么区别呢
都是用的
SL
那个模板 , 判断条件不一样而已看啦一圈很不错,关于check的问题,就前1,2情景下,您已经封装好,就不需要再考虑check,其他还是需要考虑?我做一下二分的题目,谢谢分享
不好意思刚刚翻了评论才看到, check就是边界判断, 这个得多做题,我现在也不知道怎么跟你说。
if(q[mid]>=x)r=mid; 这个是为什么啊
就是1 2 2 3 4 4 5,比如你要查询2,但是中间的a[mid]是3,比2大,那么要找的数字就在a[mid]的左边,所以就让r等于mid把区间缩小
okok谢谢大佬
为什么要写两种情况很好奇,一般的题只写一种不就够了
因为有边界限制, 如果你输入的序列含有重复数字, 你使用俩个代码查找的数字 是一样但是下标不同。 相同的值,但不是同一个元素,可以再多看几遍就明白了。
1:找大于等于数的第一个位置 (满足某个条件的第一个数)
2:找小于等于数的最后一个数 (满足某个条件的最后一个数)
这个是基于含有重复数字序列中才会区分左右边界
那如果没有重复数字呢,比如二分答案的题(计蒜客 - T1891),我试了第二种模板可以,第一种模板会超时
这个题是查找最值问题,只能用俩个模板其中一个,请重新阅读下:1:找大于等于数的第一个位置 (满足某个条件的第一个数)
2:找小于等于数的最后一个数 (满足某个条件的最后一个数)
3.查找最大值 (满足该边界的右边界)、
4.查找最小值 (满足该边界的左边界)
``