arrays - 字符串插补搜索

Question

对于不熟悉插值搜索的人，这是一种在排序数组中搜索值的方法，该值可能比二进制搜索要快。您查看第一个和最后一个元素，并(假定数组的内容均匀分布)进行线性插值以预测位置。

例如:我们有一个长度为100的数组，其中array [0] = 0和array [99] = 99。如果我们正在寻找80，那么直接在array [50]上尝试array [80]是很直观的，如果数组接近均匀分布，则预期的运行时间将减少为log(log(N))
对于数字，要检查的位置由以下公式定义:
low + ((toFind - sortedArray[low]) * (high - low + 1)) / (sortedArray[high] - sortedArray[low])。

用来展示插值搜索的直观性质的一个常见示例是:设想尝试在字典中查找单词“yellow”。您将不会使用二进制搜索并转到中间点。而是，您将转到预期的位置。

人类自然可以线性地对字符串进行插值，但是我不知道如何编码。
我们如何线性内插字符串？

Answer 1

要找到两个字符串之间的“距离”，一种简单的方法是查看两个字符串之间不同的第一个字母，并为每个字符串分配一个数值，然后取其差值。

例如，如果为每个字母分配的值等于其在字母表中的位置，则从“a”到“y”的距离将为24，从“y”到“z”的距离将为1。

一种性能更好的方法将通过字典来对各种字母进行加权，以使其在实际单词中的通用性更高。

另一种改进是查看两个字符-例如，“aa”距“bz”远比“az”距“ba”远。超过两个字符不会给您带来多少好处。

这种方法不受欢迎的原因是，它使二进制搜索算法变得复杂，获得的 yield 却很少。如果要定时的话，您甚至可能会发现标准的二进制搜索更快。在较少的比较中获得的结果在确定距离的复杂性中将丢失。

还要注意，该算法的最坏情况性能比二进制搜索要差。考虑例如在“aa”，“ab”，“ac”，“ad”，“ae”，“zz”的列表中搜索“ae”-异常值“zz”将使搜索偏向始终尝试搜索范围的开始。在这些条件下，它会降解为O(n)。