歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

順序查找的優化方法

我們知道折半查找的速度比順序查找要快很多,但前提是折半查找需要有序的數組。講解在注釋裡面~

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
由此可見,少了一個判斷,速度是有所提高的~

Copyright © Linux教程網 All Rights Reserved