我們知道折半查找的速度比順序查找要快很多，但前提是折半查找需要有序的數組。講解在注釋裡面~
package go.derek;
import java.util.Random;
public class Search {
//這個是普通的順序查找，for循環裡面每執行一次都要判斷一下i<=arr.length
//這個是會消耗時間的
public int seqSearch(int[] arr,int key){
for(int i=1;i<=arr.length;i++){
if(arr[i-1]==key){
return i;
}
}
return 0;
}
//這個是優化之後的，循環裡面只有一個判斷
//技巧就是將數組第一個設置為查找的關鍵字
//如果n最後=0了，就說明arr[0]一直到最後是沒有key了。
public int seqSearch_plus(int[] arr,int key){
int n=arr.length-1;
arr[0]=key;
while(arr[n]!=key){
n--;
}
return n;
}
//這是一個java實現的折半查詢
public int binarySearch(int[] arr,int key){
int low=1;
int mid=0;
int high=arr.length;
while(low<=high){
mid=(low+high)/2;
if(key<arr[mid-1]){
high=mid-1;
}
else if(key>arr[mid-1]){
low=mid+1;
}
else
return mid;
}
return 0;
}
public static void main(String[] args){
int[] arr=new int[40000000];
for(int i=0;i<arr.length;i++){
arr[i]=new Random().nextInt(10000000)+1;
}
long n=System.currentTimeMillis();
int x=new Search().seqSearch(arr, 666615888);
long m=System.currentTimeMillis();
System.out.println(x);
System.out.println("順序查詢耗時："+(m-n)+"ms");
long a=System.currentTimeMillis();
int y=new Search().seqSearch_plus(arr, 666615888);
long b=System.currentTimeMillis();
System.out.println(y);
System.out.println("優化之後順序查詢耗時："+(b-a)+"ms");
long p=System.currentTimeMillis();
}
}
由於查詢的是一個不可能出現的數，所以兩個方法都是找不到的，肯定都返回0
運行結果顯示：
0
順序查詢耗時：131ms
0
優化之後順序查詢耗時：114ms
由此可見，少了一個判斷，速度是有所提高的~
