二分查找

记忆最简单的一种

  • 开区间，不加减，更新左右的时候直接更新，不需要加1减1这种操作
  • 要什么，第一个判断就是什么，比如需要小于等于，那么第一个判断就是中点值是否小于等于
  • 第一个是什么，返回什么，比如第一个判断是小于等于，小于等于自然更新的是$l$，因此答案就是$l$

小于等于目标的最大位置

1
2
3
4
5
6
7
8
9
int find(int[] a, int q) {
    int l = -1, r = a.length;
    while (l + 1 < r) {
        int m = (l + r) >> 1;
        if (a[m] <= q) l = m;
        else r = m;
    }
    return l;
}

大于等于目标的最小位置

1
2
3
4
5
6
7
8
9
int find(int[] a, int q) {
    int l = -1, r = a.length;
    while (l + 1 < r) {
        int m = (l + r) >> 1;
        if (a[m] >= q) r = m;
        else l = m;
    }
    return r;
}