这两天在刷二分的题，因为当初没学好，被搞得很难受，经过这几天多次思考，多道题目的折磨，坐牢了几个下午，稍微悟了一小点，分享一下！！

本文提示：本文不做详细证明，如果想看证明可以看点赞第一的那位大佬的文章（实在没那能力）

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/

感谢阅读！

推荐一个dfs专题