数据结构 - 索引查找

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

二进制搜索比线性搜索具有时间复杂性的巨大优势.线性搜索具有最坏情况下的复杂度O(n)而二进制搜索具有O(log n).

有些情况下可以提前知道目标数据的位置.例如，如果是电话簿，我们想要搜索Morphius的电话号码.在这里，线性搜索甚至二进制搜索似乎都很慢，因为我们可以直接跳转到存储名称从"M"开始的存储空间.

二进制搜索中的定位

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

即使数据已排序，二进制搜索没有利用来探测所需数据的位置.

插值搜索中的位置探测

插值搜索通过计算探测器找到特定项目位置.最初，探测位置是集合中间项目的位置.

如果匹配发生，那么项目的索引是回.要将列表拆分为两部分，我们使用以下方法 :

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

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

插值搜索算法的运行时复杂度为Ο(log(log n))与BST的Ο(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.

Pseudocode

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

要了解C编程语言中插值搜索的实现.