2.11 性能对比：顺序查找与二分查找

 顺序查找：

public static int orderSearch(int[] nums,int k){
    for(int i = 0;i<nums.length;i++){
        if(nums[i]==k){
            return i;
        }
    }
    return -1;
}

//不难发现,顺序查找的时间复杂度为O(n)

二分查找（折半查找）：

  //二分查找的前提是有序

public static int binSearch(int[] nums,int k){
    int i = 0;
    int j = nums.length-1;
    int mid;
    while(i<=j){
        mid = i+((j-i)>>1);//防止溢出,移位效率更高
        if(nums[mid]==k){
            return mid;
        }else if(nums[mid]<k){
            i = mid + 1;
        }else{
            j = mid - 1;
        }
    }
    return -1;
}

• 第1次 剩余的数为n/2
• 第2次 剩余的数为n/4
• 第3次 剩余的数为n/8
• ....以此类推
• 第k次 剩余的数为n/(最后剩余的数应该是1)
• 所以n/=1
• n = 
• 所以时间复杂度为O(logn)

  顺序查找与二分查找的性能比较

•    从时间复杂度上来看顺序查找的时间复杂度为O(n),也就是说面对的数据顺序查找所需要耗费的时间为1s
•    二分查找的时间复杂度为O(),面对的数据所需要耗费的时间为 s
•    很明显二分查找所耗费的时间比顺序查找少了很多很多
•    用程序跑出来也是差不多的结果

package 第二章;

import java.util.Scanner;

public class Main {
	public static int orderSearch(int[] nums,int k){
	    for(int i = 0;i<nums.length;i++){
	        if(nums[i]==k){
	            return i;
	        }
	    }
	    return -1;
	}
	public static int binSearch(int[] nums,int k){
	    int i = 0;
	    int j = nums.length-1;
	    int mid;
	    while(i<=j){
	        mid = i+((j-i)>>1);//防止溢出,移位效率更高
	        if(nums[mid]==k){
	            return mid;
	        }else if(nums[mid]<k){
	            i = mid + 1;
	        }else{
	            j = mid - 1;
	        }
	    }
	    return -1;
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		System.out.print("请输入你要查找的数: ");
		int k = in.nextInt();
		int[] nums = new int[100000000];
		for (int i = 0; i < nums.length; i++) {
			nums[i] = i+1;
		}
		int indexOf = -1;
		long beginTime = System.currentTimeMillis();
		indexOf = orderSearch(nums, k);
		long endTime = System.currentTimeMillis();
		System.out.println("顺序查找所耗费的时间为: "+(endTime-beginTime)+"ms,该数在数组中的索引为: "+indexOf);
		beginTime = System.currentTimeMillis();
		indexOf = binSearch(nums, k);
		endTime = System.currentTimeMillis();
		System.out.println("二分查找所耗费的时间为: "+(endTime-beginTime)+"ms,该数在数组中的索引为: "+indexOf);
	}
}

  跑出来的结果是:

  

  可见顺序查找的所耗费的时间为二分查找的很多倍了