顺序查找的优化技巧

发布时间：2021-12-13 11:45:52 所属栏目：PHP教程来源：互联网

导读：我们知道折半查找的速度比顺序查找要快很多，但前提是折半查找需要有序的数组。讲解在注释里面~ package go.derek; import java.util.Random; public class Search { //这个是普通的顺序查找，for循环里面每执行一次都要判断一下i=arr.length //这个是会消耗

我们知道折半查找的速度比顺序查找要快很多，但前提是折半查找需要有序的数组。讲解在注释里面~

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
由此可见，少了一个判断，速度是有所提高的~

（编辑：云计算网_泰州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

php批量命名文件技巧	php读取文件内容几种正
php中读取大文件实现方	php打开远程文件的方法