二分查找细则

关于二分查找

二分查找或许是很多人学习的第一个算法，其简洁明快，但是在实际应用中，你却会看到许多种写法的二分查找，而这些写法，仅是细节处的区别。

这些不同写法的二分查找，究竟哪一个才是正确的？还是，无论怎么写，达到目的便可以称之为二分查找？

常规写法一

public static int bSearch(int[] arr, int start, int end, int key){

    while (start <= end){
        // 防止溢位
        int mid = start + (end - start)/2;
        if (arr[mid] == key)	return mid;
        if (arr[mid] > key)
            end = mid - 1;
        else
            start = mid + 1;
    }

    return -1;
}

这种写法便是我所学习的，或许也是大多数人所学习的，如果存在，其查找过程如下：

如果目标不存在，则查找过程如下所示：

如上种写法，注意，在参数传入的时候，数组的两边都是封闭的，也就是说，在传入数组的时候，需要传入 length-1 ，使得 end =length-1。

常规写法二

但是，好多人可能还见到过另一种写法：

public static int bSearch(int[] arr, int start, int end, int key){

    while (start < end){
        // 防止溢位
        int mid = start + (end - start)/2;
        if (arr[mid] == key)	return mid;
        if (arr[mid] > key)
            end = mid;
        else
            start = mid + 1;
    }

    if (start >= arr.length)	return -1;
    return arr[start] == key ? start : -1;
}

注意此种写法与上种写法的差异：

start <= end 变为 start < end
end = mid - 1 变为 end = mid

经过以上改动，其传参之时，便是一个左闭右开的区间了，如需传入整个数组，则直接传入 length 即可，

那么为何如此？

一与二的差异

第一种与第二种写法，实质上是相同的，而所产生了写法上差异的原因，本质在于区间范围的不同。

和所有算法一般，代码希望不重复，不遗漏地解决问题，故产生了两种不同的细节。

写法一的细节

正如我在写法一最后所说，写法一的左右区间都是封闭的。

end = mid - 1
- 在搜索判断的时候，只要arr[mid] > key的时候，我们接下来要做的便只是缩短区间，将区间缩为 [start, mid-1]
- 由于此区间便是左右封闭的，那么直接写为end = mid - 1 即可。
start <= end
- 为何这么写？答为：为了方便。
- 如果写为 start < end，那么，代码有可能在 start == end 的时候终止，而 key 有可能恰好就在 start 处，这时候，返回 -1 显然是不合适的。
- 写为 start < end 可不可以？
  - 可以，当然，你需要在跳出循环之后进一步判断，当然，此时不能单纯地使用 arr[start] ，可能会超出数组索引，比较麻烦。

写法二的细节

第二种写法一开始便认为区间是左闭右开的。

end = mid - 1
- 同样地，arr[mid] > key之时，也需要缩短区间至 [start, mid-1]
- 由于第二种写法是左闭右开的，也就是说要将区间缩为 [start, mid)，故需要写为 end = mid
start < end
- 为何这么写？答为：为了不陷入死循环。
- 和上面为了方便不同，此处如果写为 <= 便会直接出错
  - 如果写为 <= 如果此时刚好 mid == start == end 并且 arr[mid] > key ，便一直会执行 end == mid，从而导致 start === end，从而造成死循环！
  - 第一种写法则不同，其是 end = mid - 1 ，可以直接跳过。

查找左侧边界

当数组有重复元素时，比如：[1, 2, 2, 2, 2, 3, 4, 5]，此时若需要寻找一个元素，我们更希望寻找到一个边界的元素，比如寻找 2 ，我们更希望寻找到最左边的 2 或者是最右边的 2。

寻找左侧边界，便是这种寻找最左边元素的二分算法。

首先贴出代码让大家感受一番：

public static int lowerBound(int[] arr, int start, int end, int key){

    while (start < end){
        // 防止溢位
        int mid = start + (end - start)/2;
        if (arr[mid] >= key)
            end = mid;
        else
            start = mid + 1;
    }

    return start;
}

有了上面对于细节的描述，我想，现在便可以很容易地看出：

上边的代码会停在最左边的元素上（如果有这个元素的话）。
上边的代码会停在小于查找的元素中最大的那个上（如果没有这个元素的话）

查找右侧边界

代码如下：

public static int upperBound(int[] arr, int start, int end, int key){

    while (start < end){
        // 防止溢位
        int mid = start + (end - start)/2;
        if (arr[mid] > key)
            end = mid;
        else
            start = mid + 1;
    }

    return start;
}