二分查找的细节实现

二分查找的一些细节

1. 什么是二分查找

对于已经排序的表(假设该表是升序)，，假设目标值在闭区间[l, r]中， 每次将区间长度缩小一半，当l = r时，我们就找到了目标值。

2. 二分查找容易遇到的问题

  二分查找原理简单，但是如果细节处理不好，容易出现错误答案，甚至是死循环的结果。网上给出的模板甚多，这里只给出Y大的模板。如下

3. 模板

  原模板是C++版，如下已改为java版。

3.1 给出要查找数的左边界

如要查找升序数组中数4第一次出现的位置：[3, 3 , 4, 4, 4, 4, 4, 6, 8, 9]，结果应该为2；
如查找升序数组中第一个大于4(大于4的数中的左边界)的数：[3, 3 , 4, 4, 4, 4, 4, 6, 6, 8, 9 ]，结果应该为7;
注意第二种情况，并不是找4，找大于4的数，所以是大于4的数左边界。

  当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid(取被划分的左区间)，或者l = mid + 1(取被划分的右区间)，计算mid时不需要加1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public int binarySearch(int l, int r) {
    while (l < r) {
        int mid = (left + right) >> 1;
        // 如果满足在左子表的条件
        if (check(mid)) {
            r = mid;
        } else {
            // 取右子列表
            l = mid + 1;
        }
    }
    // 跳出循环时l=r,返回哪个都一样
    return l;
}

3.2 给出要查找数的右边界

如要查找升序数组中数4第最后一次出现的位置：[3, 3 , 4, 4, 4, 4, 4, 6, 8, 9]，结果应该为6；
如查找升序数组中最后一个小于4(小于4的数当中的右边界)的数：[3, 3 , 4, 4, 4, 4, 4, 6, 6, 8, 9 ]，结果应该为1;
注意第二种情况，并不是找4，找小于4的数，所以是小于4的右边界。

  当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid，此时为了防止死循环，计算mid时需要加1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public int binarySearch2(int l, int r) {
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        // 如果满足在右子表的条件
        if (check(mid)) {
            l = mid;
        } else {
            // 取左子表
            r = mid - 1;
        }
    }
    // 跳出循环时l=r,返回哪个都一样
    return l;
}

4. 总结

4.1 如何选择模板

  假设答案为N, 满足条件的数为o，不满足条件的数为x，
当数组为xxxxNoooo，这时答案为所有符合条件的值的最左边，所以应该使用第一种左边界的模板。
当数组为oo0oNxxxx，这时答案为所有符和条件的值的最右边，所以应该使用第二种右边界的模板。

4.2 记忆

确定左边界模板：

1. 左边界：mid = (l + r) >> 1
2. 满足条件选左子表，if(check(mid)) { r = mid } ; check满足的条件下，直接=mid，不需要+1。
3. 不满足条件，l = mid + 1；(如果是要右区间，l = mid + 1；如果要左区间，r = mid - 1)。

确定右边界模板：

1. 左边界：mid = (l + r + 1) >> 1
2. 满足条件选右子表，if(check(mid)) { l = mid } ; check满足的条件下，直接=mid，不需要+1。
3. 不满足条件，r = mid - 1；(如果是要右区间，l = mid + 1；如果要左区间，r = mid - 1)。