如何简单描述插值查找算法的基本原理？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1175个文字，预计阅读时间需要5分钟。
插值查找和二分查找类似，是针对有序表的查找算法。其基本原理是：基于有序性，将查找点与中间点进行比较，根据比较结果缩小查找范围，逐步逼近目标值。具体描述如下：
二分查找是通过对有序表进行折半查找的方法，每次都将查找范围缩小一半。具体步骤如下：
1. 初始化：确定查找范围的起始位置low和结束位置high。
2.循环查找：当low <=high时，执行以下步骤：
a. 计算中间位置mid=(low + high) / 2。 b. 比较查找点与中间点： - 如果查找点等于中间点，则查找成功，返回mid。 - 如果查找点小于中间点，则将查找范围缩小到mid左侧，即high=mid - 1。 - 如果查找点大于中间点，则将查找范围缩小到mid右侧，即low=mid + 1。3.查找失败：当low > high时，表示查找失败，返回-1。）
二分查找是通过折半的方法，每一次都将搜索范围缩小至原来的二分之一，如果这个折半能够实现到折四分之一甚至更多，效率将会更高。
插值查找就是这样的算法，类似于二分查找，插值查找每次会从自适应处开始查找，实质上是将 \(\frac1 2\) 处位置的查找公式做了修改：
\[mid = \frac{low + high}{2} = low + \frac{1}{2}(high - low) \Rightarrow mid = low + \frac{key - a[low]}{a[high] - a[low]}(high - low) \]插值查找详细的执行步骤如下：
- 在有序表中，通过比例公式取对应记录作为比较对象；
- 若给定值与对应记录的关键字相等，则查找成功；
- 若给定值小于对应记录的关键字，则在对应记录的左半区继续查找；
- 若给定值大于对应记录的关键字，则在中间记录的右半区继续查找；
- 不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。
打个比方，在一本英文字典中查找 apple 这个单词的时候，肯定不会从字典中间开始查找，而是从字典开头部分开始翻，因为会觉得这样的找法才是比较快的。
对于一个有序的序列，如果能在查找前较准确的预测关键字在序列中的位置时，这样的查找方法能比二分查找拥有更好的性能。
其中的差值公式 \(\frac{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);
}
}
首发于翔仔的个人博客，点击查看更多。
本文共计1175个文字，预计阅读时间需要5分钟。
插值查找和二分查找类似，是针对有序表的查找算法。其基本原理是：基于有序性，将查找点与中间点进行比较，根据比较结果缩小查找范围，逐步逼近目标值。具体描述如下：
二分查找是通过对有序表进行折半查找的方法，每次都将查找范围缩小一半。具体步骤如下：
1. 初始化：确定查找范围的起始位置low和结束位置high。
2.循环查找：当low <=high时，执行以下步骤：
a. 计算中间位置mid=(low + high) / 2。 b. 比较查找点与中间点： - 如果查找点等于中间点，则查找成功，返回mid。 - 如果查找点小于中间点，则将查找范围缩小到mid左侧，即high=mid - 1。 - 如果查找点大于中间点，则将查找范围缩小到mid右侧，即low=mid + 1。3.查找失败：当low > high时，表示查找失败，返回-1。）
二分查找是通过折半的方法，每一次都将搜索范围缩小至原来的二分之一，如果这个折半能够实现到折四分之一甚至更多，效率将会更高。
插值查找就是这样的算法，类似于二分查找，插值查找每次会从自适应处开始查找，实质上是将 \(\frac1 2\) 处位置的查找公式做了修改：
\[mid = \frac{low + high}{2} = low + \frac{1}{2}(high - low) \Rightarrow mid = low + \frac{key - a[low]}{a[high] - a[low]}(high - low) \]插值查找详细的执行步骤如下：
- 在有序表中，通过比例公式取对应记录作为比较对象；
- 若给定值与对应记录的关键字相等，则查找成功；
- 若给定值小于对应记录的关键字，则在对应记录的左半区继续查找；
- 若给定值大于对应记录的关键字，则在中间记录的右半区继续查找；
- 不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。
打个比方，在一本英文字典中查找 apple 这个单词的时候，肯定不会从字典中间开始查找，而是从字典开头部分开始翻，因为会觉得这样的找法才是比较快的。
对于一个有序的序列，如果能在查找前较准确的预测关键字在序列中的位置时，这样的查找方法能比二分查找拥有更好的性能。
其中的差值公式 \(\frac{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);
}
}
首发于翔仔的个人博客，点击查看更多。