java数据结构和算法——插值查找算法

一、插值查找算法介绍

• 插值查找算法类似于二分查找，必须是有序列表，不同的是插值查找每次从自适应mid(即获取数组中间的索引)处开始查找。
• 将二分查找(即折半查找)中的求mid 索引(即获取数组中间的索引)的公式:int mid=(left+right)/2 改成 int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) 。
• 代码和二分查找(即折半查找)类似，唯独mid的计算方式发生改变。

二、插值查找算法注意事项

• 对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找, 速度较快.
• 关键字分布不均匀的情况下，插值查找算法不一定比二分查找算法(折半查找算法)要好

三、举例说明插值查找算法 1-100 的数组

假如我们需要查找的值分别 为1和100

• 使用二分查找算法需要多次递归，才能找到 1和100
• 使用插值查找算法查找值为1时，利用 int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])公式，int mid = 0 + (99 - 0) * (1 - 1)/ (100 - 1) = 0 + 99 * 0 / 99 = 0 ，一次查找就可找到
• 使用插值查找算法查找值为100时，利用 int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])公式，int mid = 0 + (99 - 0) * (100 - 1)/ (100 - 1) = 0 + 99 * 99 / 99 = 99，一次查找就可找到

四、插值查找算法示例

1、代码

package com.rf.springboot01.dataStructure.search;

/**
 * @description: 插值查找算法示例
 * @author: xiaozhi
 * @create: 2020-08-18 22:44
 */
public class InsertSearch {
    public static void main(String[] args) {
        //生成一个1到100的有序数组
        int[] arr=new int[100];
        for(int i=0;iright || findValuearr[arr.length-1]){
            return -1;
        }
        // 求出mid即中间位置索引, 自适应
        int  mid=left + (right - left) * (findValue - arr[left]) / (arr[right] - arr[left]);
        int midValue=arr[mid];//中间位置索引的值
        if(findValue>midValue){//向右递归
            return insertSearch(arr,mid+1,right,findValue);
        }else if(findValue