//查找左边界 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; }
关于记忆:有减必有加
左边界:边界最左边的数,右边界同理.
一般二分应用于无非下面这四种情况:
1:找大于等于数的第一个位置 (满足某个条件的第一个数)
2:找小于等于数的最后一个数 (满足某个条件的最后一个数)
3.查找最大值 (满足该边界的右边界)、
4.查找最小值 (满足该边界的左边界)
然后每次使用这这两个模板的时候,先想是找这个区间的左端点还是还是右端点,然后选择用模板,最后再去写判断条件。如果你是新手,模板题做完,可以去找几道同类型算法题练练巩固下,我新手的时候就是没这样做555
推荐习题: 四平方和 分巧克力 机器人跳跃问题
下面这俩道是洛谷, 应用的3 和4 查找最值
https://www.acwing.com/blog/content/21312/
https://www.acwing.com/solution/content/118815/
下面是这道题的代码
#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; }
标签:二分,return,边界,int,mid,整数,查找,while,详解 From: https://www.cnblogs.com/NGDBZ/p/16988919.html