深入：二分查找算法（分治）

前言：
二分查找算法也称折半搜索算法，对数搜索算法，是一种在有序数组中查找某一特定元素的搜索算法。

形象图：
动图演示点击查看

循环实现：

 	
    private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                                     long key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            long midVal = a[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

java中>>>是什么意思？

‘>>>’是java中的移位运算符，表示无符号右移。

移位运算符面向的运算对象也是二进制的“位”。可单独用它们处理整数类型（主类型的一种）。

“有符号”左移位运算符（<<）能将运算符左边的运算对象向左移动运算符右侧指定的位数（在低位补0）。

“有符号”右移位运算符（>>）则将运算符左边的运算对象向右移动运算符右侧指定的位数。“有符号”右移位运算符使用了“符号扩展”：若值为正，则在高位插入0；若值为负，则在高位插入1。

Java 也添加了一种“无符号”右移位运算符（>>>），它使用了“零扩展”：无论正负，都在高位插入0。

递归实现：

    
    private static int binarySearch0(int[] nums, int start, int end, int target) {
        if (nums == null || start > end) {
            return -1;
        }
        int mid = (start + end) >> 1;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            return binarySearch0(nums, start, mid - 1, target);
        } else {
            return binarySearch0(nums, mid + 1, end, target);
        }
    }

我们可以比较一下二者的优缺点：

总结：实践检验真知！