二分查找的优雅写法

二分查找的优雅写法

---

根据返回值的要求不同，二分查找有以下几种（假定我们在一个整数数组中查找某个value）

0 二分查找的分类

有下面几种形式的要求：

1. 如果存在，返回true，否则返回false。
2. 如果存在，返回第一次出现的索引值，否则返回-1。
3. 如果存在，返回第一次出现的索引值，否则返回-(1 + 可插入的位置)。可插入的位置指的是第一个大于等于查找值位置的索引。
4. 如果存在，返回第一次出现的索引和最后一次出现的索引，否则返回[-1, -1]。

所有的要求都可以用下面将要讲到的lower和upper函数解决：

1 求第一个大于等于查找值的位置

我们在前开后闭区间[first, last)中递归地查找，返回第一个大于等于value的位置；如果所有数字都小于value，那么返回last。
这个返回值实际上也是value应该插入的位置。

int lower(int[] array, int value) {
    int first = 0, last = array.length;
    while (first < last) { // 当[fisrt, last)非空时
        int mid = first + (last - first) / 2; // 避免溢出
        if (array[mid] < value) {
            first = mid + 1;
        } else {
            last = mid;
        }
    }
    return first; // 与last相等，返回last也行
}

2 求第一个大于查找值的位置

我们在前开后闭区间[first, last)中递归地查找，返回第一个大于value的位置；如果所有数字都小于等于value，那么返回last。

int upper(int[] array, int value) {
    int first = 0, last = array.length;
    while (first < last) { // 当[fisrt, last)非空时
        int mid = first + (last - first) / 2; // 避免溢出
        if (array[mid] <= value) { // 和上面比只有这里不同
            first = mid + 1;
        } else {
            last = mid;
        }
    }
    return first; // 与last相等，返回last也行
}

3 求最后一个小于(等于)查找值的位置

这两个位置可以通过前两个函数得到的位置-1得到。
比如最后一个小于查找值的位置就是第一个大于等于查找值的位置-1。也许你要对查找值不存在时的情况做一个额外判断。

4 求某一个值的出现范围/次数

int[] range(int[] array, int value) {
    int start = lower(array, value);
    int end = upper(array, value);
    return new int{start, end};
}

int count(int[] array, int value) {
    return upper(array, value) - lower(array, value); 
}

5 示例

array: [1, 1, 2, 2, 2, 3, 4, 5]

• lower(array, 2) = 2
• upper(array, 2) = 5
• range(array, 2) = [2, 5)
• lower(array, 0) = 0
• upper(array, 0) = 0
• range(array, 0) = [0, 0)
• lower(array, 6) = 8
• upper(array, 6) = 8
• range(array, 6) = [8, 8)