二分查找的递归与非递归写法

卷旗夜劫单于帐，乱斫胡儿缺宝刀。——马戴《出塞词》

时间复杂度：O(Nlog^N),查询效率虽然高，但是条件必须是待查元素必须有序。

非递归：int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};

 /**
     * 二分查找的常规写法
     *
     * @param array 待查数组
     * @param k     查询值
     *              left 左边界
     *              right 右边界
     *              middle 二分边界
     */
 public static void binarySerach(int[] array, int k) {
        int left = 0;
        int right = array.length - 1;
//        int middle = (left + right) / 2;//存在溢出问题
        int middle = left + ((right - left) >> 1);//括号一定得加
        while (left <= right) {            
            /*在中间值右边，缩小区间*/
            if (k > array[middle]) {
                left = middle + 1;
                /*在中间值右边，缩小区间*/
            } else if (k < array[middle]) {
                right = middle - 1;
                /*找到了*/
            } else {
                System.out.println("I find it:key=" + k + "====>" + "array[" + middle + "] :" + array[middle]);
                return;
            }
            /*缩小二分边界*/
            middle = (left + right) / 2;
        }
        System.out.println("I cant find");
    }

递归版本：

    /**
     * 二分查找的递归写法
     *
     * @param array 待查数组
     * @param k     查询值
     * @param left  左边界
     * @param right 右边界
     *              middle 二分边界
     */
    public static void binarySerachRecursion(int[] array, int k, int left, int right) {
//        int middle = (left + right) / 2;
        /*定义二分边界*/
        int middle = left + ((right - left) >> 1);
        /*递归出口*/
        if (left > right) {
            System.out.println("its not exist");
            return;
        }
        if (k > array[middle]) {
            binarySerachRecursion(array, k, middle + 1, right);
        } else if (k < array[middle]) {
            binarySerachRecursion(array, k, left, middle - 1);
        } else {
            System.out.println("I find it:key=" + k + "====>" + "array[" + middle + "] :" + array[middle]);
            return;
        }
    }

检测一下：使用最容易出问题的边界值来测一下

binarySerach(bsarray, 9);
binarySerachRecursion(bsarray, 9, 0, bsarray.length - 1);

//+++++++++++++++++++++++++++++++++
I find it:key=9====>array[8] :9
I find it:key=9====>array[8] :9

推荐使用普通版本，递归版本时间复杂度和普通版本是一样的。