二分的平均时间复杂度是O(logn)，最好情况是O(1)，最坏也是O(logn）！！！！！！！！！！！！！！！

整数二分

单调性的一定可以二分，但是可以二分的不一定要单调性

二分的本质：

只要一个区间内存在一割性质可以将区间一分为二，那么二分就可以找到两个边界（因为是整数二分，所以边界值不会重合）

• 计算左边边界（红色）和右边边界（绿色）有两个不同的做法

二分步骤：

1. 红色边界：
   1. 找中间值$mid=\frac{l+r+1}{2}$
   2. 判断中间值是否满足红色性质
   3. 如果mid满足红色性质
      • 边界点在区间[mid,r]
        • 包含mid，因为mid有可能是边界值
      • 更新方式：把[l,r]区间更新成[mid,r]，即l=mid
   4. 如果mid不满足红色性质
      • 边界点在区间[l,mid-1]
        • 不包含mid，因为mid已经不满足条件了
      • 更新方式：r = mid-1
2. 绿色边界：
   1. 找中间值$mid=\frac{l+r}{2}$
   2. 判断中间值是否满足绿色性质
   3. 如果mid满足绿色性质
      • 边界点在区间[l，mid]
        • 包含mid，因为mid有可能是边界值
      • 更新方式：把[l,r]区间更新成[l,mid]，即r=mid
   4. 如果mid不满足绿色性质
      • 边界点在区间[mid+1,r]
        • 不包含mid，因为mid已经不满足条件了

• 为什么第一个板子的mid计算要$mid=\frac{l+r+1}{2}$
  • 假设l=r-1，即相差只有1时，如果mid没有+1，那计算得到的mid就会等于l（向下取整）
  • 那如果check是True，那l、r更新后就还是[l,r]
  • 如果补上+1，那mid等于r，最后如果check=True，l更新后就变成r，就会停止循环

二分板子

//c++
//区间[l,r]被划分成[l,mid-1]和[mid,r]
int bsearch1(int l, int r){
		while(l < r){
				int mid = l + r + 1 >> 1;
				if(check(mid)) l = mid;
				else r = mid - 1;
		return l;
}
//区间[l,r]被划分成[l,mid]和[mid+1,r]
int bsearch2(int l, int r){
		while(l < r){
				int mid = l + r >> 1;
				if(check(mid)) r = mid;
				else l = mid + 1;
		return l;
}

# python
def bsearch1(arr, x, l, r): # arr是数组，x是用来check需要的值，l、r是数组区间
    while(l < r):
        mid = (l + r + 1) // 2
        if check(arr,mid,x):
            l = mid
        else:
            r = mid - 1
    return l
def bsearch2(arr, x, l, r):
    while(l < r):
        mid = (l + r) // 2
        if check(arr,mid,x):
            r = mid
        else:
            l = mid + 1
    return l

如何利用板子？

给一道题，如何判断它满足哪个板子

1. 先写$mid=\frac{l+r}{2}$
2. 再写一个check函数代入mid，然后想一下check函数为True或False的话如何更新
3. 如果更新方式要l=mid，那mid就要补上1
4. 如果更新方式为r=mid，那mid就不用补1