Java教程

java查找算法:插值查找

本文主要是介绍java查找算法:插值查找,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

差值查找思路:


在讲解这个公式之前,我们需要先知道差值查找的思路是什么。
二分查找的思路是:直接分一半,然后每次处理一半。但是假如我们找的值在最左边,或者最右边,那么就必须一次一次分割到最后才行了。

那么有没有可能我可以把查找范围缩到更小,缩小到上次数组的1/3、1/4或者更小?这就是差值查找算法要做的事情,把查找的范围缩的得更小。
 

插值查找介绍:

  1. 插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。
  2. 将二分查找中的mid索引的公式,left表示左边索引,right表示右边索引,findVal就是
  3. 代码公式:int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);

java代码实现: 

public class InsertValueSearch {
    public static void main(String[] args) {
int arr[]={1,2,3,4,5,6,7,8,9,10};
int index=insertValueSearch(arr,2,0,arr.length-1);
System.out.println(index);
}
// int arr[]:待查找的有序数组
//int findVal :查找的值
//int left:左边索引
int right :右边索引
public static int insertValueSearch(int arr[],int findVal,int left,int right){
//先进行判断,如果左边索引>右边索引,直接返回-1。当findVal小于数组arr的最小值或者大于数组arr的最
//大值,则查找不到该数,直接返回-1
if(left>right||findVal<arr[left]||findVal>arr[right]){
return -1;
}
//找到中间下标
 int mid=left+(rigth+left)*(findVal-arr[left])/(arr[right]-arr[left])
//找到中间值
int midVal=arr[mid];
//进行判断
//如果findVal小于中间值,则在数组的左边,进行左边递归
if(findVal<arr[mid]){
insertValueSearch(arr,findVal,mid+1,right);
}else if(
//如果findVal大于中间值,则在数组的右边,进行右边递归
insertValueSearch[arr,findVal,left,mid-1);
)else{
//找到了该值,返回对应的下标
return mid;
}
}
}

插值查找注意事项

  1. 对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找,速度较快
  2. 关键字分布不均匀的情况下,该方法不一定比二分查找要好
这篇关于java查找算法:插值查找的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!