插值查找的简单理解
2023-02-19 12:17:29 时间
详细描述
二分查找是通过折半的方法,每一次都将搜索范围缩小至原来的二分之一,如果这个折半能够实现到折四分之一甚至更多,效率将会更高。
插值查找就是这样的算法,类似于二分查找,插值查找每次会从 自适应 处开始查找,实质上是将 \(\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)
\]
插值查找详细的执行步骤如下:
- 在有序表中,通过比例公式取对应记录作为比较对象;
- 若给定值与对应记录的关键字相等,则查找成功;
- 若给定值小于对应记录的关键字,则在对应记录的左半区继续查找;
- 若给定值大于对应记录的关键字,则在中间记录的右半区继续查找;
- 不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止。
问题解疑
插值查找为什么是 \(\frac{key - a[low]}{a[high] - a[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);
}
}
相关文章
- Jgit的使用笔记
- 利用Github Action实现Tornadofx/JavaFx打包
- 叹息!GitHub Trending 即将成为历史!
- 微软软了?开源社区讨论炸锅,GitHub CEO 亲自来答
- GitHub Trending 列表频现重复项,前后端都没去重?
- Photoshop Elements 2021版本软件安装教程(mac+windows全版本都有)
- (ps全版本)Photoshop 2020的安装与破解教程(mac+windows全版本都有)
- (ps全版本)Photoshop cc2018的安装与破解教程(mac+windows全版本,包括2023
- 环境搭建:Oracle GoldenGate 大数据迁移到 Redshift/Flat file/Flume/Kafka测试流程
- 每个开发人员都要掌握的:最小 Linux 基础课
- 来撸羊毛了!Windows 环境下 Hexo 博客搭建,并部署到 GitHub Pages
- 超实用!手把手入门 MongoDB:这些坑点请一定远离
- 【GitHub日报】22-10-09 zustand、neovim、webtorrent、express 等4款App今日上新
- 【GitHub日报】22-10-10 brew、minio、vite、seaweedfs、dbeaver 等8款App今日上新
- 【GitHub日报】22-10-11 cobra、grafana、vue、ToolJet、redwood 等13款App今日上新
- Photoshop 2018 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2017 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2020 下载及安装教程(mac+windows全版本都有,包括最新的2023)
- Photoshop 2023 资源免费下载(mac+windows全版本都有,包括最新的2023)
- 最新版本Photoshop CC2018软件安装教程(mac+windows全版本都有,包括2023