2
插值查找的简单理解 - 程序员翔仔
source link: https://www.cnblogs.com/fatedeity/p/16448493.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
二分查找是通过折半的方法，每一次都将搜索范围缩小至原来的二分之一，如果这个折半能够实现到折四分之一甚至更多，效率将会更高。
插值查找就是这样的算法，类似于二分查找，插值查找每次会从自适应处开始查找，实质上是将 12 处位置的查找公式做了修改：
mid=low+high2=low+12(high−low)⇒mid=low+key−a[low]a[high]−a[low](high−low)
插值查找详细的执行步骤如下：
- 在有序表中，通过比例公式取对应记录作为比较对象；
- 若给定值与对应记录的关键字相等，则查找成功；
- 若给定值小于对应记录的关键字，则在对应记录的左半区继续查找；
- 若给定值大于对应记录的关键字，则在中间记录的右半区继续查找；
- 不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。
插值查找为什么是 key−a[low]a[high]−a[low]?
打个比方，在一本英文字典中查找 apple 这个单词的时候，肯定不会从字典中间开始查找，而是从字典开头部分开始翻，因为会觉得这样的找法才是比较快的。
对于一个有序的序列，如果能在查找前较准确的预测关键字在序列中的位置时，这样的查找方法能比二分查找拥有更好的性能。
其中的差值公式 key−a[low]a[high]−a[low] 是要将查找的关键字与序列中的最大、最小记录的关键字比较，获取一个相对更准确的位置。
使用插值查找有哪些注意事项？
对于均匀分布的序列，插值查找的效率是非常快。特别是对于绝对均匀分布的序列（相邻元素差值相同），插值查找可以只做一次比较就查找成功。
对于分布很不均匀的序列，插值查找的计算则会起到反效果，这时候反而不如二分查找。
package cn.fatedeity.algorithm.search; public interface Search { int search(int[] numbers, int target);}
插值查找类
package cn.fatedeity.algorithm.search; /** * 插值查找类 */public class InterpolationSearch implements Search { private int search(int[] numbers, int target, int left, int right) { if (left > right) { return -1; } else if (left == right) { if (numbers[left] == target) { return left; } else { return -1; } } if (target < numbers[left] || target > numbers[right]) { return -1; } int scale = (target - numbers[left]) / (numbers[right] - numbers[left]); int mid = left + (int) Math.floor(scale * (right - left)); if (numbers[mid] > target) { return this.search(numbers, target, left, mid - 1); } else if (numbers[mid] < target) { return this.search(numbers, target, mid + 1, right); } else { return mid; } } @Override public int search(int[] numbers, int target) { return this.search(numbers, target, 0, numbers.length - 1); }}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK