数据结构和算法插值搜索


插值搜索是二进制搜索的改进变体。该搜索算法适用于所需值的探测位置。为使此算法正常工作,数据收集应采用排序形式并均匀分布。

二进制搜索与线性搜索相比具有时间复杂性的巨大优势。线性搜索具有Ο(n)的最坏情况复杂度,而二分搜索具有Ο(log n)。

存在可以预先知道目标数据的位置的情况。例如,如果是电话目录,我们是否要搜索Morphius的电话号码。在这里,线性搜索甚至二进制搜索看起来都很慢,因为我们可以直接跳转到存储名称从“M”开始的存储空间。

定位二进制搜索

在二进制搜索中,如果未找到所需数据,则列表的其余部分分为两部分,即较低和较高。搜索是在其中任何一个中进行的。

BST第一步 BST第二步 BST第三步 BST第四步

即使对数据进行排序,二进制搜索也不会利用探测所需数据的位置。

插值搜索中的位置探测

插值搜索通过计算探测位置来找到特定项目。最初,探针位置是集合中间项目的位置。

插值第一步 插值第二步

如果发生匹配,则返回该项的索引。要将列表拆分为两部分,我们使用以下方法 -

mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

where 
   A    = list
   Lo   = Lowest index of the list
   Hi   = Highest index of the list
   A[n] = Value stored at index n in the list

如果中间项大于项,则再次在中间项右侧的子阵列中计算探测位置。否则,在中间项左侧的子阵列中搜索该项。该过程也在子阵列上继续,直到子阵列的大小减小到零。

与有利情况下的BST的 Ο(log n) 相比,插值搜索算法的运行时复杂度是 Ο(log(log n))**

算法

由于它是现有BST算法的即兴创作,我们提到了使用位置探测搜索“目标”数据值索引的步骤

Step 1  Start searching **data** from middle of the list.
Step 2  If it is a match, return the index of the item, and exit.
Step 3  If it is not a match, probe position.
Step 4  Divide the list using probing formula and find the new midle.
Step 5  If data is greater than middle, search in higher sub-list.
Step 6  If data is smaller than middle, search in lower sub-list.
Step 7  Repeat until match.

伪代码

A  Array list
N  Size of A
X  Target Value

Procedure Interpolation_Search()

   Set Lo    0
   Set Mid  -1
   Set Hi    N-1

   While X does not match

      if Lo equals to Hi OR A[Lo] equals to A[Hi]
         EXIT: Failure, Target not found
      end if

      Set Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])

      if A[Mid] = X
         EXIT: Success, Target found at Mid
      else
         if A[Mid] < X
            Set Lo to Mid+1
         else if A[Mid] > X
            Set Hi to Mid-1
         end if
      end if
   End While

End Procedure