数据结构和算法学习--插值查找算法

Leefs 2020-02-06 PM 1604℃ 0条

# 数据结构和算法学习--插值查找算法

（1）插值查找原理介绍：

插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。

（2）将折半查找中的求mid索引的公式，low表示左边索引left,hight表示右边索引right.

key就是前面我们讲的findVal

![24.插值查找算法01.png][1]

（3）int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;/*插值索引*/
 对应前面的代码公式：
 int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])

（4）举例说明插值查找算法1-100的数组

> 插值查找算法的 举例说明 
>
> 数组 arr = [1, 2, 3, ......., 100]
>
> 假如我们需要查找的值 1
>
> 使用二分查找的话，我们需要多次递归，才能找到 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 = 0 + (99 - 0) * (100 - 1) / (100 - 1) = 0 + 99 * 99 / 99 = 0 + 99 = 99

**插值查找应用案例**

请对一个有序数组进行插值查找{1,8,10,89,1000,1234},输入一个数看看该数组是否有此数，并且求出下标，如果没有就提示“没有这个数”。

**代码实现**

```java
public class InsertValueSearch {
    public static void main(String[] args) {

int arr[]={1,8,10,89,1000,1000,1234};
        int index = insertValueSearch(arr,0,arr.length-1,1234);
        System.out.println("index="+index);
    }
    public static int insertValueSearch(int[] arr,int left,int right,int findVal){
        System.out.println("插值查找次数~");
        //注意：findVal<arr[0] 和 findVal>arr[arr.length-1]必须需要
        //否则我们得到的mid可能越界
        if(left>right||findVal<arr[0]||findVal>arr[arr.length-1]){
            return -1;
        }

//求出mid,自适应
        int mid=left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
        int midVal=arr[mid];
        //当left > right时，说明递归整个数组，但是没找到
        if(left>right){
            return -1;
        }
        if(findVal > midVal){//向右递归
            return binarySearch(arr,mid+1,right,findVal);
        }else if(findVal < midVal){
            return binarySearch(arr,left,mid-1,findVal);
        }else{
            return mid;
        }
    }
}
```

> 运行结果

```
插值查找次数~
index=6
```
**插值查找注意事项：**

（1）对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找。

（2）关键字分布不均匀的情况下，该方法不一定比折半查找要好

[1]: https://lilinchao.com/usr/uploads/2020/02/935685712.png

标签: 数据结构和算法, 查找

非特殊说明，本博所有文章均为博主原创。

如若转载，请注明出处：https://lilinchao.com/archives/557.html

上一篇数据结构和算法学习--二分查找算法

下一篇数据结构和算法学习--菲波那切（黄金分割法）查找算法

数据结构和算法学习--插值查找算法

评论啦~

栏目分类

标签云

友情链接申请

数据结构和算法学习--插值查找算法

 评论啦~

 栏目分类

标签云

友情链接申请

评论啦~

栏目分类

标签云

友情链接申请