精华内容
下载资源
问答
  • 插值查找算法

    2021-02-03 11:12:47
    一、插值查找算法基本思想 插值查找是一种在有序数组(前提条件)中查找某一特定元素的查找算法。插值查找基于二分查找**,不同的是插值查找每次从自适应mid处开始查找**,提高查找效率。 二分查找查找点和插值查找...

    一、插值查找算法基本思想

    插值查找是一种在有序数组(前提条件)中查找某一特定元素的查找算法。插值查找基于二分查找**,不同的是插值查找每次从自适应mid处开始查找**,提高查找效率。

    二分查找查找点和插值查找查找点计算如下:
    在这里插入图片描述
    其中key为待查找元素,low为待查找区间左端,high为待查找区间右端,mid为自适应查找点
    插值查找将上述的比例参数1/2改进为自适应,根据待查找元素在整个有序数组中所处的位置,使mid值的变化更靠近待查找元素key,可以间接地减少了比较次数。

    二、代码实现

    1、递归方式

    package Search;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class InsertValueSearch {
    	public static int insertvaluesearch(int arr[],int value,int low,int high) {
    		while(low<=high) {
    			int mid=low+(high-low)*(value-arr[low])/(arr[high]-arr[low]);//插值查找中间索引公式
    			if(arr[mid]==value) {//若中间位置值等于我们所需要查找值,即返回中间值
    				return mid;
    			}
    			if(arr[mid]<value) {//若中间位置值小于我们所需查找值,则向右递归且将下界值变为mid+1
    				return insertvaluesearch(arr,value,mid+1,high);
    			}
    			if(arr[mid]>value) {//若中间位置值大于我们所需查找值,则向左递归将上界值变为mid-1
    				return insertvaluesearch(arr,value,low,mid-1);
    			}
    		}
    		return -1;
    	}
    
    	public static void main(String[] args) {
    		int[] arr= {31,17,5,47,11,33,3,19,13,59,1,43,41,37,7,53,29};
    		Arrays.sort(arr);//采用插值查找时,需要对该数组进行排序
    		Scanner sc=new Scanner(System.in);
    		System.out.println("请输入查找元素:");
    		int value=sc.nextInt();
    		System.out.printf("查找元素 %d 的位置是 %d ",value,insertvaluesearch(arr,value,0,arr.length-1));
    	}
    }
    

    运行结果:

    请输入查找元素:
    37
    查找元素 37 的位置是 11
    

    2、非递归方式

    package Search;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class InsertValueSearch {
    	public static int insertvaluesearch(int arr[],int value) {
    		int low=0;//指针low表示待查元素所在范围的下界,下界索引从0开始
    		int high=arr.length-1;//指针high表示待查元素所在范围的上界
    		while(low<=high) {
    			int mid=low+(high-low)*(value-arr[low])/(arr[high]-arr[low]);//插值查找中间索引公式
    			if(arr[mid]==value) {//若中间位置值等于我们所需要查找值,即返回中间值
    				return mid;
    			}
    			if(arr[mid]<value) {//若中间位置值小于我们所需查找值,则向右递归且将下界值变为mid+1
    				low=mid+1;
    			}
    			if(arr[mid]>value) {//若中间位置值大于我们所需查找值,则向左递归将上界值变为mid-1
    				high=mid-1;
    			}
    		}
    		return -1;
    	}
    	public static void main(String[] args) {
    		int[] arr= {31,17,5,47,11,33,3,19,13,59,1,43,41,37,7,53,29};
    		Arrays.sort(arr);//采用插值查找时,需要对该数组进行排序
    		Scanner sc=new Scanner(System.in);
    		System.out.println("请输入查找元素:");
    		int value=sc.nextInt();
    		System.out.printf("查找元素 %d 的位置是 %d ",value,insertvaluesearch(arr,value));
    	}
    }
    

    运行结果:

    请输入查找元素:
    43
    查找元素 43 的位置是 13 
    

    三、插值查找算法的注意事项

    (1)对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找时速度较快。
    (2)在关键字分布不均匀的情况下,插值查找不一定比折半查找好

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,224
精华内容 489
关键字:

插值查找算法