二分查找(Java)

目录

非递归方法

递归方法

二分查找（Binary Search）算法，也叫折半查找算法。二分查找针对的是一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

二分查找法的运行时间为对数时间O(㏒₂n)，即查找到需要的目标位置最多只需要㏒₂n步，假设从[0,99]的队列(100个数，即n=100)中寻到目标数30，则需要查找步数为㏒₂100,即最多需要查找7次(2^6<100<2^7)

非递归方法

public class BinarySearchNorecursion {
    //非递归
    public static void main(String[] args) {
        int arr[] = {1,2,5,6,7,8,12,20,23,56,48,99};
        int i = binarySearch(arr, 48);
        System.out.println(i);
    }

    public static int binarySearch(int[] arr,int target){
        int left = 0;
        int right = arr.length-1;

        while (left<=right){//继续查找
            int mid = (left+right)/2;
            if (target == arr[mid]){
                return mid;
            }else if (target>arr[mid]){
                left = mid+1;
            }else {
                right  = mid -1;
            }
        }
        return -1;//没找到
    }
}

递归方法

public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {1, 2, 13, 24, 35, 48, 50, 56, 57, 68, 99};
        System.out.println(binarySearch(arr, 0, arr.length - 1, 56));
    }

    public static int binarySearch(int[] arr, int left, int right, int findVal) {
        if (left > right) {
            return -1;//没有找到
        }
        int mid = (left + right) / 2;
        if (findVal > arr[mid]) {
            return binarySearch(arr, mid + 1, right, findVal);//向右递归
        } else if (findVal < arr[mid]) {
            return binarySearch(arr, left, mid - 1, findVal);//向左递归
        } else {
            return mid;//找到返回
        }
    }
}