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

Question

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

就我而言，我在 --- n A 数组中有一个排序值（可以是任何类型值），如果我正在查看的值在 A[n] and A[n+1]

原文由 uray 发布，翻译遵循 CC BY-SA 4.0 许可协议

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 课程的第 12 和 13 讲： http://courses.csail.mit.edu/6.851/spring07/lec.html

原文由 jonderry 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

是的，您可以做得更好（ www.agdresearch.com ），实际上快 8 倍 8 * O(log(n)。诀窍是将键/条目拆分为重要的 ascii 字符，其中间隔有 junk-dna。同样的技巧适用于快速排序和 BTree。

该算法称为 NoChop（它不需要切分到二进制或更高的分区 - 上述方法为每个节点提供多达 256 个分支）。启用该算法的数据结构称为 STree（在保存密钥的中央稀疏矩阵之后的稀疏树）。

原文由 Andrew Guthrie 发布，翻译遵循 CC BY-SA 4.0 许可协议