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

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

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

时间复杂度：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

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