c++ - 比有序列表的二进制搜索更快

Question

有没有比二分查找更快的算法来搜索数组的排序值？

在我的情况下，我在 A 数组中有一个排序值(可以是任何类型值)，如果我正在寻找的值是，我需要返回 n在 A[n] 和 A[n+1]

的范围内

Answer 1

如果值是整数，你可以做得比 O(log n) 更好，在这种情况下，你可以达到的最佳最坏情况运行时间，就 n 而言，是 O(sqrt(log n))。否则，除非输入序列中有模式，否则无法击败 O(log n)。在整数的情况下，有两种方法可以击败 O(log n)。

首先，您可以使用 y-fast 树，它通过将所有前缀存储在哈希表中来工作，您至少要为其存储一个带有该前缀的整数。这使您能够执行二进制搜索以查找最长匹配前缀的长度。这使您能够在 O(log w) 时间内找到要搜索的元素的后继元素，其中 w 是单词中的位数。虽然有一些细节需要工作才能使这项工作正常工作并且只使用线性空间，但它们还不错(请参阅下面的链接)。

其次，您可以使用融合树，它使用位技巧使您能够在恒定数量的指令中执行 w^O(1) 比较，产生 O(log n/log w) 的运行时间。

这两种数据结构之间的最佳权衡发生在 log w = sqrt(log n) 时，运行时间为 O(sqrt(log n))。

有关上述内容的详细信息，请参阅 Erik Demaine 类(class)的第 12 课和第 13 课:http://courses.csail.mit.edu/6.851/spring07/lec.html