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

如果值是整数，则比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