插值查找

来自计算思维百科
跳转至: 导航搜索
插值查找1.png

我们想在给定的数据中找到自己想要的数据,就是查找。插值查找是一种高效的查找方法,他是在有序集合中,根据查找键的值来估计这个元素可能出现的位置,在这个预测的位置附近开始查找。

基本概念

假设我们有一个从小到大排序好的序列,我们知道最大的元素和最小的元素,若我们要查找x,根据x的大小,就可以估计出它距离最大或最小的元素的大致距离,如果x比较大,就接近最大的值,否则接近最小的值。估计x的位置的方法利用线性插值。

我们可以设集合A两端元素:(l,A[l]),(r,A[r]),查找的元素如果是x,则对应的位置大致就在插值查找2.png附近。

应用范围

插值查找的方法是在有序序列上进行查找的有效方法,可以应用到需要查找的各种问题中。

使用方法及步骤

  1. 确定集合有序和查找键的值x;
  2. 利用式(1)来确定与查找键比较的元素下标;
  3. 若A[v]=x,查找成功,结束算法;若A[v]>x,则查找范围的两端变为:(l,A[l]),(v-1,A[v-1]);

若A[v]<x,则查找范围的两端变为:((v+1,A[v+1] ),(r,A[r]));继续2。

应用案例

应用1-查字典

案例:小红手里有一本英语字典,她想查到单词computer,怎样可以快速的查到?

解决步骤:

查字典是一个很好的体现了插值查找的例子。

  1. 字典是严格按照字母顺序排列的,查找的单词为computer
  2. 首字母为c,在26个英文字母中大概在前面1/9的位置,将字典翻到前1/9处
  3. 在1/9处的单词与computer比较,若没有,再在c开头的单词范围内来确定第二个字母为o的单词所在的范围,o大概在15/26处,在c的15/26范围内查找比较;重复此查找方法。

应用2-通讯录里查找名字

案例:在存了较多人的通讯录里查找Zack的电话号码,如何快速查到?

解决步骤:

这个问题相信很多人都有经验。在现在的大多数通讯软件里,都设置了根据首字母将界面跳至某位置,这正是插值查找的一个典型的用法。

  1. 首字母为z,我们可以大概确定它在名单的最后面;
  2. 第二个字母为a,则Zack应该在z打头的名字中的最前面;
  3. 第三个字母为c,Zack应在前两位为Za的前面部分;
  4. 确定了前三位为Zac的名字范围,最后一为位k,应在Zac的单词中的中间部分,找到Zack,查找结束。

可以体现的计算思维

从插值查找的过程中,我们容易看出,我们总是根据期望能估计一个位置,在这个位置附近能查找到需要的元素,并在此过程中把范围缩小利用一样的方法去寻找可能范围。打个比方,比如我们能在lil开头的单词表里找到lily,那我们就一定能在li开头的单词表里找到lily,也就一定能在l打头的单词表里找到lily;我们求解的过程则是上述的逆过程,这个过程正是将问题分解成范围更小的等价问题,正是计算思维中问题约减的规约思想。