如何写好二分查找？

说来惭愧，9月份之后因为各种各样的原因停更了3个月，眼看2019就要过去了，想着怎么着也要来一篇给2019收个尾吧。那么今天我们就开启一个新的话题——算法。

二分查找的思路大家都清楚，典型的分治实现方式。然而结合自己过去的经历，想正确地写出一个二分实现似乎又很难，几乎每次都会有各种各样的问题。正如Donald Knuth所说的那样：

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky.

思路很简单，细节是魔鬼。

那么今天，我们就来看看二分查找中有哪些细节是值得我们重视的，避免一不小心再掉坑里了。

首先，我们看一下典型的二分查找实现方式：

public class BinarySearchTest {

    private int target = 4;

    private int[] array = new int[]{1, 3, 4, 5};

    public static void main(String[] args) {
        BinarySearchTest binarySearch = new BinarySearchTest();
        binarySearch.binarySearch();
    }

    private int binarySearch() {
        int left = 0;
        int right = array.length - 1;
        int middle = 0;
        while (left < right) {
            middle = (left + right) / 2;
            System.out.println("left = " + left + ", right = " + right + ", middle = " + middle);
            if (array[middle] > target) {
                right = middle - 1;
            }else {
                left = middle;
            }
        }

        System.out.println("left = " + left + ", right = " + right + ", middle = " + middle);
        return left;
    }
}

你能看出以上这段代码有什么问题吗？

有，还很多。不过这里我们先卖个关子，一点一点往下看。

中位数索引的计算

最常见的中位数索引计算方式是这样的：

int middle = (left + right) / 2;

如果写出这样的中位数索引计算方式，不客气地讲，你对二分查找还没入门。原因很简单，当left和right的值都很大时，(left + right)很有可能导致整型溢出。因此进阶版的方式是像下面这样：

int middle = left + (right - left) / 2;

这种方式虽然有所改进，但实质上还是没有完全避免整型溢出的问题。当right很大且left为负数的时候，依然存在同样的风险。正确的方式应该是这样：

int middle = (left + right) >>> 1;

看到这里，有同学可能有疑问了。同样是(left + right)，这种方式不是一样可能导致整型溢出吗？

别急，要回答这个问题，我们需要先弄清楚Java中右移运算符(>>) 和无符号右移运算符(>>>)的区别。

顾名思义，>>和>>>的区别在于作右移运算时是否需要处理符号位。具体来说是这样的：

• 右移运算符 >> 在右移时，丢弃右边指定位数，左边补上符号位，右移运算后被操作数的符号保持不变。
• 无符号右移运算符 >>> 在右移时，丢弃右边指定位数，左边补上 0，也就是对于正数来说，二者一样，而负数通过 >>> 后能变成正数。

说来拗口，看个例子吧：

public static void main(String[] args) {
    int left = (1 << 31 - 1);
    int right = (1 << 31 - 1);
    System.out.println("left = " + left + ", right = " + right);
    System.out.println("left + right = " + (left + right));
    System.out.println("(left + right) / 2 = " + (left + right) / 2);
    System.out.println("(left + right) >> 1 = " + ((left + right) >> 1));
    System.out.println("(left + right) >>> 1 = " + ((left + right) >>> 1));
    System.out.println((-2147483648) >>> 1);
}

==========================================
left = 1073741824, right = 1073741824
left + right = -2147483648
(left + right) / 2 = -1073741824
(left + right) >> 1 = -1073741824
(left + right) >>> 1 = 1073741824

思考题：(-4 >>> 1)结果是几呢？2、-2抑或其他？

那是不是意味着我们在二分查找中计算中位数索引时，可以无脑使用>>>呢？当然也不是。因为如果(left + right)的结果不是因为整型溢出导致的负数，而是本身正确结果就是负数的时候，就不能使用>>>了。不过在绝大多数二分查找的场景中，left和right都是表示索引的非负数，因此后两种方式都是可取的。但考虑到移位运算的高效性，个人更推荐使用>>>的方式，事实上在JDK1.8中Arrays类也大量使用了这种方式。

左右中位数的选择

首先解释下左右中位数的概念。看以下两个数组：

[1, 2, 3, 4, 5] ---- left = 0, right = 4, middle = 2
[1, 2, 3, 4] ---- left = 0, right = 3, middle = ?(1还是2)

第一个数组元素个数为奇数，毫无疑问中位数是3，对应索引middle=2。

但针对元素个数为偶数的场景，比如第二个数组，中位数其实有两个选择：2或3。其中2就是所谓的左中位数，而3自然就是右中位数。

左右中位数的索引计算方式也是有所区别的：

int mid = (left + right) >>> 1;

得到的就是左中位数索引，而

int mid = (left + right + 1) >>> 1;

得到的就是右中位数的索引了。

当然，针对元素个数为偶数的场景，两者并无区别。

既然中位数有左右之分，那问题来了：我们应该如何选择？

答案也很简单：选择左右中位数的唯一标准就是避免死循环。

什么意思呢？回到文章开头的那个例子，运行一下你会发现程序陷入了死循环，输出结果一直是这样的：

left = 2, right = 3, middle = 2
left = 2, right = 3, middle = 2
...

不难发现，发生死循环是因为某种原因导致左右边界没有收敛。而这里所谓的某种原因其实就是左右中位数的选择与分支逻辑不匹配导致的。

死循环往往发生在区间中只剩下两个元素的时候，此时在分支逻辑中选择左边界的时候，我们并没有排除掉中位数(left = middle)，而进入下一次循环的时候，中位数选择的又恰恰是左中位数，从而导致区间无法收敛。

找到的原因，解决起来也就简单了，分支逻辑不变，中位数选择右中位数即可。

同样，如果分支逻辑中选择有边界是没有排除中位数，那么中位数必须选择做中位数。

循环退出条件

凡涉及循环的操作，都要特别关注的一点就是循环退出条件，在二分查找中也不例外。这里稍有不慎也可能导致死循环的发生。

还是回到文章开头那个例子，如果我们将循环条件中的 < 改为 <=，也就是：

while (left <= right) 

那么即使你选择了正确的中位数，程序依然会发生死循环，此时left = right = middle。

为了避免这种情况导致的死循环，使用 < 当然是一种方式。还有一种方式是增加一个分支逻辑，对中位数是否为目标元素作单独判断。修改后的代码如下：

private int binarySearch() {
    int left = 0;
    int right = array.length - 1;
    int middle = 0;
    while (left <= right) {
        middle = (left + right + 1) / 2;
        System.out.println("left = " + left + ", right = " + right + ", middle = " + middle);

        if (array[middle] == target) {
            return middle;
        }

        if (array[middle] > target) {
            right = middle - 1;
        }else {
            left = middle + 1;
        }
    }
  
    System.out.println("left = " + left + ", right = " + right + ", middle = " + middle);
    return -1;
}

使用这种方式，即使在循环退出条件中不小心使用了<=，也不用担心死循环的发生。而且增加一个分支逻辑还有一个好处是不用考虑左右中位数的问题了，因为此时不论怎样，区别一定是会一直收敛下去的。

总结

本文梳理了一下二分查找中的坑，总结下来在二分查找中要注意以下几点：

• 计算中位数索引时，要防止整型溢出的风险，尽量使用无符号右移运算符。
• 循环退出条件尽量使用<，使用 <= 要重点关注可能死循环的风险。
• 处理分支逻辑时，最好增加一个分支逻辑对中位数进行单独判断。
• 如果你实在只想写两个分支逻辑，也不是不行，但这时要选择正确的中位数，避免死循环的发生。