博客

package com.wei.demo.Annotation;

/**
 * 二分查找算法Java:循环方法和递归方法
 * 思想：我们查找的数组范围是low（0）~high（len-1)。每次查找中间的元素，我们猜测的数字是guess=(low+high)/2;
 * 实际数字为item,如果猜测数字guess小于item,那范围变为：guess+1~high,low=guess+1位置开始；
 * 如果猜测数字guess大于item,那就范围变为low~guess-1
 * 数组：必须是有序的
 * 结果：返回想要数字的位置
 */
public class binary_search {

    public static void main(String[] args) {
        int[] array = {1, 2, 33, 55, 66, 88, 99, 567, 789, 999,1000,10001,100002};
       // index(array,item);
        System.out.println("循环方法猜测数字的位置为："+index(array,33));
        System.out.println("递归方法猜测数字的位置为："+binarySearch(array,0,array.length-1,33));
    }

 /**
     * 循环的方法
     * @param array
     * @param key
     * @return
     */
    public static int index(int array[],int key){

        int low = 0;
        int high = array.length - 1;
        int middle = 0;
       // int guess = array[middle];//猜测的数字

        if (key < array[low] || key > array[high] || low >high){
            return -1;
        }
        while (low <=high){ //循环结束的条件是左边等于右边，那就是中间要找的数字
            middle = (low + high)/2;
            int guess = array[middle];//猜测的数字
            if (guess < key){ //如果猜测的数字小于实际数字，low就要从middle+1开始
                low = middle + 1;
            }else if (guess > key){//如果猜测的数字大于实际数字，那么high就要从middle-1开始
                high = middle - 1;
            }else{
                return middle;
            }

        }
        return -1;
    }
    /***
     *递归的方式
     */
    public static int binarySearch(int[] arrays,int low,int high,int key){
        if (key < arrays[low] || key > arrays[high] || low >high){
            return -1;
        }
        int middle = (low + high) / 2;
        if (arrays[middle] > key){
           return  binarySearch(arrays, low, middle - 1, key);
        }else if (arrays[middle] < key){
           return  binarySearch(arrays, middle + 1, high, key);
        }else{
            return middle;
        }

    }
}

1.时间复杂度分析：

最坏的情况下两种方式时间复杂度一样：O(log2 N)

最好情况下为O（1）

2.空间复杂度分析：

算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数


循环方式：


由于辅助空间是常数级别的所以：

空间复杂度是O(1);


递归方式：

递归的次数和深度都是log2 N,每次所需要的辅助空间都是常数级别的：

空间复杂度：O(log2N )