二分用来干嘛?

用来找到满足某种性质的区间的边界

二分查找有两种写法, 应对的场景不同, 从代码上看最核心的区别在于求 mid 下标时是否需要加一来求出 mid 下标

二分的本质

存在一个性质, 通过这个性质我们可以把整个区间分成左右两个部分, 使得右半部分满足这个性质, 左半部分不满足这个性质, 左右两边没有交点(整数二分)

如果这个性质存在, 那么就可以通过二分来找到满足性质的区间的边界点

如上图, 找到左边界的端点(红色点)或者找到右边界的端点(绿色点)对应的就是两个模板

找红点

来看看找到红点对应的模板:

二分分成以下几步

①找到中间点 mid

$mid=\frac{l+r+1}{2}$ 然后判断这个中间点是否满足我们的红色性质

if(check(mid))

② a. check 为 true , 那么说明 mid 一定满足红色性质, 那么此时答案一定在 [mid, r] 之间, 因为 mid 有可能是答案, 所以是闭区间, 因为我们要找的是端点, 所以肯定不会在已经满足性质的 mid 左边, 那么这个时候我们就可以更新区间为 $[mid, r]$ 则令 l=mid

② b. check 为 false, 那么说明 mid 不满足红色性质, 此时答案一定在 mid 的左边, 那么更新区间为 $[l, mid-1]$, 则令r=mid-1

1
2
3
4
5
6
7
8


int binarySearchLPoint(int l, int r) {
  while(l < r) {
    int mid = l + r + 1 >> 1;
    if(check(mid)) l = mid;
    else r = mid-1;
  }
  return l;
}

找绿点

来看看找到红点对应的模板:

二分分成以下几步

①找到中间点 mid

$mid=\frac{l+r}{2}$ 然后判断这个中间点是否满足我们的红色性质

if(check(mid))

② a. check 为 true, 那么说明 mid 一定满足绿色性质, 此时答案一定在[l, mid]之间, 因此,更新区间为$[l, mid]$, 则令r=mid

②b. check 为 false, 那么说明 mid 不满足绿色性质, 此时答案一定在 mid 的右边, 因此更新区间为$[mid+1, r]$, 则令l=mid+1

1
2
3
4
5
6
7
8


int binarySearchRPoint(int l, int r) {
  while(l < r) {
    int mid = l + r >> 1;
    if(check(mid)) r = mid;
    else l = mid+1;
  }
  return l;
}

使用二分的考虑事项

直接写出 mid = l + r >> 1
考虑 check 函数为 true时区间是如何变化的, 如果变成 l=mid, 那么回过头来修改第一步的 mid = l + r + 1 >> 1 , 如果变成 r=mid
确定把区间一分为二的性质到底是什么,也就是 check 函数到底是什么然后根据这个性质判断我应该如何变换区间才能找到想要的边界点.

该性质把我想要的数放到了右区间, 那么我就只能找想要的数的第一个点, 即 r = mid. 因为后面的点就无法通过性质去取到了, 所以只能去找第一个点

该性质把我想要的数放到了左区间, 那么我只能找想要的数的最后一个点, 即 l = mid; mid=l+r+1>>1 , 因为左边的点无法通过性质去取到想要的值了, 所以只能找最后一个点

理解这第三点很重要!!!

除非是专门找起点终点, 不然直接默认找第一个点就行, 也就是:

$mid = l + r » 1$

check函数保证想要的数出现在右区间

Q&A

Q1 为什么找红点的时候 mid 需要+1 再求

A1 假设我们不加一看看会发生什么: 因为当 $l = r-1$ , 也就是 $l 和 r$是相邻的时候, 由于大多数编程语言都是向下取整, 所以此时求出来 $mid = \frac{l+r}{2} = \frac{l+l+1}{2} = \frac{2l}{2} + \frac{1}{2}向下取整没了= l$ , 即 $mid = l$ , 然后进行区间更新l = mid= l , 那么那么这次循环就没把区间更新, 就会导致死循环,

如果加一了, 那么区间就能更新为 l=l+1=r , 此时就可以正常退出 for 循环了

Q2 单调性和二分的关系是什么?

A2 有单调性必定能用二分, 用二分不一定有单调性. 单调性只是我们让我们使用二分的性质之一, 但不是唯一

练习题: 数的范围