算法基础课 2.5 二分查找与顺序查找

二分查找 复杂度 log2 N
顺序查找 复杂度 N

package study;

public class sort {
    public static void main(String[] args) {
        int [] x= new int [100000000];
        for(int i=0;i<x.length;i++) {
            x[i] = i+1;
        }
        int target = 100000000;
        long now = System.currentTimeMillis();
        int index = binarySearch(x,x.length-1,0,target);
        duration(now);
        System.out.println(target+"所在位置"+index);
        now = System.currentTimeMillis();
        index =search(x,target);
        duration(now);
        System.out.println(target+"所在位置"+index);
    }
    
    /**
     * 二分查找
     * @param arr
     * @param hight
     * @param low
     * @param key
     * @return
     */
    public static int binarySearch(int[] arr,int hight,int low,
                                        int key) {
        while(low<=hight) {
            int mid = low + ((hight-low)>>1);//防止溢出，移位也更高效。同时每次循环都需要更新
            int midVal = arr[mid];
            
            if(midVal>key) {
                hight = mid-1;
            }else if(midVal<key){
                low = mid +1;
            }else {
                return mid;
            }
        }
        return -(low + 1);
        
    }
    
    /**
     * 顺序查找
     * @param arr
     * @param key
     * @return
     */
    public static int search(int[] arr,int key) {
        for(int i=0;i<arr.length;i++) {
            if(arr[i]==key) {
                return i;
            }
        }
        return -1;
    }
    
    public static void duration(long x) {
        System.out.println(System.currentTimeMillis()-x+"ms");
    }
}

输出结果

0ms
100000000所在位置99999999
34ms
100000000所在位置99999999