查找算法之插值查找（深入理解，详细说明）

不念不忘少年蓝@ 2023-02-18 12:57 49阅读 0赞

回顾一下之前讲述的二分查找。其基本的思路就是找到中间值mid将序列分成两个部分，然后判断要查找的值是在左子序列还是右子序列进而继续找到中间值再分裂。可以看到，每次分裂是将原序列分成相等的两个部分，每个子序列相对于原序列所占比也就是1/2（后面提到的所占比都是这个意思）。还是拿之前的例子作比较：

**思考：对于序列\{5,8,34,55,66\}，如果想要查找‘5’这个元素，按照原先二分查找的思路，在1/2的所占比的基础上分裂，那么序列要分裂（查找）多少次呢？很明显需要2次。那么，假设我们取元素‘8’为中间值，还是查找‘5’这个元素。可以看到仅仅只需要一次比较就确定了‘5’的位置，并且此时‘5’元素的所占比为：1/5，另一部分则为3/5（去除掉了中间值）。可以看到，中间值的选取能够决定查找元素的效率，而中间值的选择跟我上面所说的“所占比”密切相关。（这里的“所占比”是我在个人理解基础上提出来的，目的是方便理解与讲述，不是规定的说法）。**

做了这么多铺垫，相信你或许知道我接下来要讲什么了。没错，接下来要讲的就是在二分查找的基础上实现的扩展——插值查找（按比例查找）。

首先介绍一些插值查找的工作原理：（以下图片都是截取自韩顺平老师的数据结构与算法教学视频）[视频链接][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center]  
如上图，经过二分查找获取中间下标的算法改成的另一个算法，这里我的理解是求出要查找值key在序列总的所占比。如果你学过数值分析相信会有更好的理解。（其实，我也是只是听别人谈到了数值统计这个名词哈哈）

接下来举例说明插值查找算法1-100的数组：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 1]  
最后给出完整的代码：

/**
         *
         * @param arr 查找数组
         * @param left 起始下标
         * @param right 末尾下标
         * @param value 查找的值
         * @return
         */
        public static int insertValueSearch(int[] arr,int left,int right,int value){
        
            //递归结束
            //没有找到
            //重点：这里value < arr[0] || value > arr[arr.length - 1]不能省
            //原因：由于需要查找的元素涉及到了求中值的算法运算，根据算法公式可知随着value的增大，mid也随之增大
            //如果如果value过于大时，mid可能越界
            if (left > right || value < arr[0] || value > arr[arr.length - 1]){
        
                return -1;
            }
            //改变过后求中间下标的算法
            int mid = left +(right - left) * (value - arr[left]) / (arr[right] - arr[left]);
            int midValue = arr[mid];
            if (value > midValue){
        //右递归
                return insertValueSearch(arr,mid + 1,right,value);
            }else if (value > midValue){
        //左递归
                return insertValueSearch(arr,left,mid - 1,value);
            }else {
        //找到了
                return mid;
            }
        }

**总结：插值查找类似与二分查找。对于数据量大的以及关键字分布均匀的有序序列来说，插值查找的速度较快。对于分布不均匀的有序序列来说，该算法不一定比二分查找要好。**

[Link 1]: https://www.bilibili.com/video/BV1E4411H73v?p=81
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200617213602678.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200617214803979.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTY0MjI1Mw==,size_16,color_FFFFFF,t_70#pic_center