Java二分法查找（递归、循环实现）

Java二分法查找（递归、循环实现）

public class BinarySearch {
    public static void main(String[] args) {
        /**
         * @author JadeXu
         * @// TODO: 2020/12/7 二分查找
         * 思路：
         * 1、获取数组的中间值，先获取下标，方便多次查找
         * 奇数位的数组直接获取中间位，偶数位的数组获取中间的第一位或第二位都可，
         * 一般获取第一位（因为与奇数位获取中间值的方法一样）
         * 2、获取查找的区间范围，start：区间开始的下标，end：区间结束的下标
         * 3、判断查找的数和中间位的数是否相同
         * 相同时，直接返回需要的数据，跳出方法
         * 大于时，即数可能在中间值右边的区间内，此时将开始下标+1，即往后移一位，
         * 就得到了中间值右边区间的开始下标。
         * 小于时，即数可能在中间值左边的区间内，此时将结束下标-1，即往前移一位，
         * 就得到了中间值左边区间的结束下标。
         * 当一个区间里，开始下标小于等于结束下标时，该区间才是有效区间，才能继续查找。
         * 否则无效，返回找不到，跳出方法。
         */
    }
    /**
     *循环
     * @param arr 已经升序好的int[]
     * @param num 需要查找的数字
     * @return 找到则返回下标，没找到则返回-1
     */
    private static int binarySearchByCycle(int[] arr,int num) {
        int start = 0;
        int end = arr.length - 1;

        while (start <= end){
            int mid = (start + end) / 2;
            if(num == arr[mid]){
                return mid;
            }else if(num > arr[mid]){
                start += 1;
            }else {
                end -= 1;
            }
        }
        return -1;
    }

    /**
     * 递归
     * @param arr 已经升序好的int[]
     * @param num 需要查找的数字
     * @param start 区间开始下标
     * @param end 区间结束下标
     * @return 找到则返回下标，没找到则返回-1
     */
    private static int binarySearchByRecursion(int[] arr,int num,int start,int end) {
        int mid = (start + end) / 2;
        if(num == arr[mid]){
            return mid;
        }else if(num > arr[mid]){
            start += 1;
        }else {
            end -= 1;
        }
        if(start <= end && num != arr[mid]){
            mid = binarySearchByRecursion(arr,num,start,end);  //递归继续寻找
        }else {
            mid = -1;
        }
        return mid;
    }
}

本文地址：https://blog.csdn.net/qq_44089205/article/details/110825668