插值查找算法(思路分析)

插值查找原理介绍:

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

②将折半查找中的求mid索引的公式进行一个修改(如下:)

• mid = (low + high)/2 = low + 1/2(high - low) 修改为 mid = low + ((key - a[low])/(a[high] - a[low])) * (high - low)
  • 那么我们为什么要让这个公式做这种修改?
    • 我们通过一个举例进行分析: 如果我们查找一个长度为100的,其中存储的数值为 1 -100的一个数组中的值为1的元素的下标,这个时候我们如果使用折半查找需要查找六次才能找到,而我们的插值算法呐?
      • 我们将1带入自适应mid计算的公式中 : mid = 0 + (1 - 1)/(100 - 1)(99 - 0) = 0 , 而0就是数组中为1的元素的下标,所以我们使用插值查找只是使用了一次就查找到了数组中的元素值为1的位置
• 所以我们发现使用插值排序算法之后一定程度上能提高我们的查找效率(相对于折半查找来讲)

我们其实可以发现: mid = low + ((key - a[low])/(a[high] - a[low])) * (high - low)公式其实就是将折半查找中求mid的公式的 1 /2改为了 ((key - a[low])/(a[high] - a[low])), 而我们的((key - a[low])/(a[high] - a[low]))其实就相当于是一个斜率,我们可以通过这个斜率定义到大致的一个待查找元素的位置, 最后面乘以一个(high - low)其实就是通过斜率找到我们想要找的元素平均分布的情况下举例low的相对位置,最终加上low就找到了对应查找的元素的位置

• 但是一旦涉及到斜率之后也会相应的有一些问题:
  ① 如果a[high] = a[low]; 那么分母就为0

  ②关键字分布不均匀的情况至之下,通过斜率计算出来的对应mid位置可能会有较大的偏差,所以数组内容分布不均匀的情况之下插值排序并不一定比折半查找好

  • 我们这里的分布不均匀是值跨越很大的那种,那么一般情况之下我们的插值排序的效率是要比折半查找的效率高的

  ③由于是斜率,所以我们如果可以的值很大,那么就有可能计算出的mid会出现越界的情况,可能是上越界,也可能是下越界

  • findVal > arr[arr.length -1会出现上越界
  • findVal < arr[0]会出现下越界
    • 所以我们一定要提前做好判断,如果findVal > arr[arr.length - 1,或者findVal < arr[0]的时候就返回 -1表示找不到

插值查找注意事项:

1. 对于数据量比较大的,关键字分布比较均匀的查找表来讲,我们采用插值查找效率比较高
2. 但是对于关键字分布不均匀的情况之下,插值查找算法并不一定比折半查找要好
   • 这里的不均匀指的指的是跳转很大的情况 , 一般情况之下我们的插值查找算法的效率还是比我们的折半查找要高的

补充:

mid = low + ((key - a[low])/(a[high] - a[low])) * (high - low)中分母a[high] - a[low]的值应该是要确保为一个正数, 所以我们其实在算法中应该将分母的值放到绝对值函数中(也就是放到Math.abs()方法中)