文档章节

常见的查找算法(三):插值查找

o
 osc_g8254g7s
发布于 2019/08/19 20:08
字数 582
阅读 12
收藏 0

精选30+云产品,助力企业轻松上云!>>>

插值搜索法(Interpolation search)是利用插值公式来计算猜测搜索键值的位置。搜索方式与二分搜索相同

 

插值公式

插值 = (设算数 -­ 最小数) / (最大数 -­ 最小数) 

搜索键值 = left + parseInt( ( key - data[ left ] ) / ( data[ right ] - data[ left ] ) ) * ( right - left ) )

 

插值搜索之算法与二分搜索算法几乎完全相同,差别在:

  • 二分搜索法:猜测键值在中间位置(middle)
  • 插值搜索法:用插值公式计算键值位置

 

插值算法代码如下:

 1     /**
 2      * 差值查找的最好的一个典型就是翻词典,当你要翻一个c开头的词,你不会打开书中间往两边查找,
 3      * 而是往靠前的那个位置去翻,插值查找就是对查找的范围查找的元素按比例做出调整。
 4      * 这种算法比较适合较大的数组,还有数组中分布的值大小要比较均匀。
 5      * <p>总结:对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好的多。
 6      * 反之,数组中如果分布非常不均匀,那么插值查找未必是很合适的选择。</p>
 7      * 本例子使用不均匀且量小的例子。所以比较的次数比较多。
 8      */
 9     public static int insertSearch(int[] a, int value, int low, int high) {
10         int mid = low + ((value - a[low]) / (a[high] - a[low])) * (high - low);
11         count++;
12         if (a[mid] == value)
13             return mid;
14         count++;
15         if (a[mid] > value)
16             return insertSearch(a, value, low, mid - 1);
17         else
18             return insertSearch(a, value, mid + 1, high);
19     }

  这种算法比较适合较大的数组,还有数组中分布的值大小要比较均匀。

  最坏时间复杂度O(n),最好时间复杂度O(1),平均时间复杂度O(log₂(log₂n))。

  测试代码:

 1     public static void main(String[] args) {
 2         int[] arr = {1, 1, 2, 0, 9, 3, 12, 7, 8, 3, 4, 65, 22};
 3 
 4         //二分查找的前提是在排好序的数组中查找
 5         QuickSort.quickSorts(arr, 0, arr.length - 1);
 6         System.out.println(Arrays.toString(arr));
 7 
 8         int result = insertSearch(arr, 4, 0, arr.length - 1);
 9 
10         if (result != -1)
11             System.out.println("在数组中的位置:" + (result + 1));
12         else
13             System.out.println("要查找的数不出存在");
14 
15         System.out.println("比较次数:"+count);
16     }
o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
有序表查找

好久没上博客园了,之前说好的一周写一个博客来记录自己的考研计划也落空了。 忙着复习,好久都没有打开电脑,计划也都是写在纸上了。最新开始数据结构的复习才打开了电脑。 开始敲代码的感觉...

osc_4g93n6bo
2018/07/17
3
0
查找算法总结

1.查找算法 查找是在大量的信息中寻找一个特定的信息元素,在计算机应用中,查找是常用的基本运算,例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法,说是七种,其实...

```...简单点
2019/09/28
0
0
数据结构与算法

笨办法学 Python · 续 练习 13:单链表 笨办法学 Python · 续 练习 13:单链表 数据结构与常见排序算法之算法篇(基于Python) 如果将最终写好运行的程序比作战场,我们码农便是指挥作战的...

掘金官方
2017/12/06
0
0
七大查找算法

1、顺序查找: 成功时间复杂度O((n+1)/2),失败:O(n)【在顺序存储或链式存储下查找】 2、二分查找: 对半查找,必须在有序的条件下,平均时间复杂度O(log2n),失败O(log2(n+1)) 3、插...

osc_jghpf0ob
2018/04/29
2
0
数据结构(六)查找---有序表查找(三种查找方式:折半,插值,斐波拉契查找)

前提 有序表查找要求我们的数据是有序的,是排序好的,我们只需要进行查找即可 我们下面将介绍折半查找(二分查找),插值查找,斐波那契查找 一:折半查找 (一)定义 二分查找也称折半查找...

osc_3md1xrlp
2018/08/19
3
0

没有更多内容

加载失败,请刷新页面

加载更多

Linux安装redis服务器和部署

Linux安装redis和部署 第一步:下载安装包 wget http://download.redis.io/releases/redis-5.0.5.tar.gz 访问https://redis.io/download 到官网进行下载。这里下载最新的5.0.5版本. 第二步:...

osc_3ytpwpyb
14分钟前
11
0
IF函数,根据条件设定输入内容

if函数通常用于条件判断,根据判断结果执行相应命令。 1.函数解释: IF(logical_test, [value_if_true], [value_if_false]) logical_test 必需。 计算结果为 TRUE 或 FALSE 的任何值或表达式...

osc_sumf8h95
15分钟前
5
0
Pytorch自定义dataloader以及在迭代过程中返回image的name

pytorch官方给的加载数据的方式是已经定义好的dataset以及loader,如何加载自己本地的图片以及label? 形如数据格式为 image1 label1 image2 label2 ... imagen labeln 实验中我采用的数据的...

osc_l8u38961
17分钟前
0
0
灯塔

\[love\ and \ share \] 我怎么感觉变成了好东西推荐呢?算了,本来也差不多 还没写完,想到再更 有好看玩的能不能评论一下,qwq 动漫 大多是些国漫,多在\(b\)站、腾讯视频、盗版小网站能够...

osc_dc6pbw3x
18分钟前
0
0
网易首页 」 网易手机 」 正文 苹果超薄触摸显示技术专利曝光:重新定义轻薄

最近,苹果公司的新屏幕专利技术已经曝光。特别是苹果公司的新型超薄触摸技术,它可以降低显示器的结构水平,消除多余的电路,并使屏幕更薄。该专利表明,这项新技术适用于iPhone,iPad,App...

osc_opzpp18v
19分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部