顺序查找和二分查找算法性能分析

顺序查找时间复杂度：O（n)

二分查找时间复杂度：O（lgn)

package 递归;

public class 顺序查找和二分查找的性能分析 {
    public static void main(String[] args) {
        int[] x=new int[10000*10000];
        for(int i=0;i<x.length;i++){
            x[i]=i+1;
        }
        int target=10000*10000;

        long now=System.currentTimeMillis();//获取当前时间
        System.out.println("顺序查找");
        int index=search(x,target);
        duration(now);
        System.out.println("二分查找");
        now=System.currentTimeMillis();
        index=binarySearch(x,0,x.length-1,target);
        duration(now);
    }

    private static void duration(long x) {
        System.out.println(System.currentTimeMillis()-x+"ms");
    }

    /**
     * 顺序查找
     */
    private 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 int binarySearch(int[] shuzu,int numberKey,int start,int end){
        int mid=(end-start)/2+start;
        if(start>end){
            return -1;
        }
        if(numberKey<shuzu[mid]){
            return binarySearch(shuzu,numberKey,start,mid-1);
        }else if(numberKey>shuzu[mid]){
            return binarySearch(shuzu,numberKey,mid+1,end);
        }else{
            return mid;
        }
    }
}

结果：

顺序查找
67ms
二分查找
0ms