顺序查找O（n）
二分查找O（lgn）
通过代码来感受性能差别
1 package recursion; 2 3 /** 4 * @author zsh 5 * @company wlgzs 6 * @create 2019-02-16 16:09 7 * @Describe 感受顺序查找与二分查找的性能差别 8 */ 9 public class Main2 { 10 11 /** 12 * 顺序查找 13 * @param arr 待查找的数组 14 * @param key 待查找的数 15 * @return 返回key在数组中所在的位置 16 */ 17 static int sequentialSearch(int[] arr,int key){ 18 for (int i = 0; i < arr.length; i++) { 19 if (arr[i] == key){ 20 return i; 21 } 22 } 23 return -1; 24 } 25 26 /** 27 * 循环实现二分查找 28 * @param arr 待查找的数组 29 * @param key 待查找的数 30 * @return key在数组中的索引位置 31 */ 32 static int binary(int[] arr,int key){ 33 //头指针初始位置 34 int low = 0; 35 //尾指针初始位置 36 int high = arr.length -1; 37 //定义middle指针位置 38 int middle = 0; 39 //头尾交叉 || key大于最大值 || key小于最小值，说明未找到 40 if (low > high || key > arr[high] || key < arr[low]){ 41 return -1; 42 } 43 44 while (low <= high){ 45 //防止数据溢出 46 middle = (low + high) >>> 1; 47 if (arr[middle] > key){ 48 //middle所对应的值比key大，key应该在左边区域 49 high = middle -1; 50 }else if (arr[middle] < key){ 51 //middle所对应的值比key小，key应该在有边区域 52 low = middle +1; 53 }else { 54 return middle; 55 } 56 57 } 58 59 //最后仍然没有找到，则返回-1 60 return -1; 61 } 62 63 public static void main(String[] args) { 64 //构造1千万的数据 65 int[] arr = new int[(int) Math.pow(10,8)]; 66 for (int i = 1; i <= (int) Math.pow(10,8) ; i++) { 67 arr[i-1] = i; 68 } 69 70 //使用顺序查找的运行时间 71 long time1 = System.currentTimeMillis(); 72 sequentialSearch(arr,1000000); 73 long time2 = System.currentTimeMillis(); 74 System.out.println(time2-time1); 75 76 //使用二分查找的运行时间 77 long time3 = System.currentTimeMillis(); 78 binary(arr,1000000); 79 long time4 = System.currentTimeMillis(); 80 System.out.println(time4-time3); 81 } 82 83 }
运行结果：
