数据结构和算法插值搜索 数据结构和算法二进制搜索 数据结构和算法哈希表 插值搜索是二进制搜索的改进变体。该搜索算法适用于所需值的探测位置。为使此算法正常工作，数据收集应采用排序形式并均匀分布。 二进制搜索与线性搜索相比具有时间复杂性的巨大优势。线性搜索具有Ο(n)的最坏情况复杂度，而二分搜索具有Ο(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 如果中间项大于项，则再次在中间项右侧的子阵列中计算探测位置。否则，在中间项左侧的子阵列中搜索该项。该过程也在子阵列上继续，直到子阵列的大小减小到零。 与有利情况下的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 数据结构和算法二进制搜索 数据结构和算法哈希表
