java二分查找

对于程序猿或者程序媛来讲，二分查找貌似并不陌生主要是循环遍历一个有序的数组找到你想要的元素。二分查找gitHub，具体图解如下：

image

当时我的想法是这就是个简单的递归算法，每次查询array[array.length/2] == number

判断第ary.length/2个元素的值是否与number相等，并返回arry中的位置。废话不多说了，直接上代码

    //在ary中通过二分查找的方式找到对应数字在ary中的位置
    public static int getOneNumberBayHalf(int [] ary,int number,int start, int end){
        if(start> end)
            return  -1;
        int mid = start +(end -start)/2;
        if (number == ary[mid]) {
            System.out.print("数字:" + number+"的位置在从ary中的第"+mid+"位");
            return mid;
        }
        if (number < ary[mid]){
            return getOneNumberBayHalf(ary,number,start,mid-1);
        }
        //if (number > ary[mid])
        else {
            return getOneNumberBayHalf(ary,number,mid+1,end);
        }
    }

递归算法如果没设计好推出逻辑很容易出现stackoverflow。确实是这样，我一开始把出口逻辑写错了。如下（以下是典型错误示范，所以大家一定要注意）：

    public static int binarySearch(int[] array, int target) {
        int low = 0, high = array.length - 1;
        while (low < high) {
            int mid =(high - low) / 2;
            if (target == array[mid]) {
                return mid;
            } else if (target > array[mid]) {
                low = mid + 1;
            } else if (target < array[mid]) {
                high = mid;
            }
        }
        return -1;
    }

执行的时候直接死循环了，毕竟是干QA的直接发现逻辑有问题于是被我优化了一下，如下：

    public static int binarySearch(int[] array, int target) {
        int low = 0, high = array.length - 1;
        while (low < high) {
            // 下面代码一定注意,否则会进入死循环
            // int mid =(high - low) / 2;
            // 正确写法如下
            int mid =low + (high - low) / 2;
            if (target == array[mid]) {
                return mid;
            } else if (target > array[mid]) {
                low = mid + 1;
            } else if (target < array[mid]) {
                high = mid;
            }
        }
        return -1;
    }

希望看完这篇文章的QA同学们以后都要注意一下开发的写法，尤其是对循环、判断、递归出口等，一定要注意一下，及时发现问题并指正！