最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

今日报丨关于整数二分的详解

来源：博客园


(资料图片仅供参考)

//查找左边界 SearchLeft 简写SLint 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 #include 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                 

关键词：         
       大于等于 
              
       小于等于 
              
       然后选择