我有一个超过十亿的排序整数，你认为哪种数据结构可以利用排序行为?主要目标是更快地搜索项目…
我能想到的选项——
1)中间方法递归分割的正则二叉搜索树。
2)任何其他平衡二叉搜索树应该工作得很好，但没有利用排序启发式。
Thanks in advance.
[编辑]
插入和删除非常罕见…
此外，除了整数，我还必须在节点中存储一些其他信息，我认为普通数组不能这样做，除非它是一个列表，对吧?
这取决于你想对数据做什么操作。
如果你只是搜索数据，从不插入或删除任何东西，只是将数据存储在一个巨大的排序数组中可能是完美的。然后你可以使用二分查找在O(log n)时间内有效地查找元素。然而，插入和删除可能会很昂贵，因为对于10亿个整数来说，O(n)会很麻烦。如果你愿意，你可以把辅助信息存储在数组本身，只要把它放在每个整数的旁边。
但是，对于10亿个整数，这可能太占用内存了，您可能想要切换到使用位向量。然后你可以在时间O(log U)内对这个位向量进行二分搜索，其中U是位的个数。对于10亿个整数，我假设U和n很接近，所以这不是什么大损失。根据机器字的大小，这可以为您节省32到128倍的内存，而不会对性能造成太大的影响。此外，这将增加二进制搜索的局部性，也可以提高性能。这确实使得在列表中实际迭代数字的速度要慢得多，但它使插入和删除花费O(1)时间。为了做到这一点，您需要存储一些二级结构(可能是哈希表?)，其中包含与每个整数相关的数据。这不是太糟糕，因为你可以使用这个排序的位向量来排序查询和未排序的哈希表，一旦你找到了你要找的。
如果您还需要从列表中添加和删除值，则平衡BST可能是一个不错的选择。然而，因为你特别知道你在存储整数，你可能想看看更复杂的van Emde Boas树结构，它支持插入、删除、前代、后代、查找最大和查找最小，所有这些都在O(log log n)时间内完成，这比二叉搜索树要快得多。然而，这种方法的实现成本很高，因为数据结构是出了名的难以正确处理的。
您可能想要探索的另一个数据结构是位树，它具有与排序位向量相同的时间界限，但允许您与每个整数一起存储辅助数据。另外，它非常容易实现!
希望这对你有帮助!
搜索有序整数的最佳数据结构是数组。
你可以用log(N)次操作来搜索它，而且它比树更紧凑(更少的内存开销)。
您甚至不需要编写任何代码(因此减少了出现错误的可能性)—只需使用标准库中的bsearch。
对于排序数组，您可以存档的最佳方法是使用插值搜索，这将为您提供log(log(n))平均时间。它本质上是一个二分搜索，但不会将数组分成两个大小相同的子数组。它非常快，而且非常容易实现。
http://en.wikipedia.org/wiki/Interpolation_search不要让最坏情况O(n)界吓到你，因为对于10亿个整数，它几乎不可能得到
0(1)个解:
- 假设32位整数和大量内存:
大小约为2³²(40亿个元素)的查找表，其中每个索引对应具有该值的整数的数量。
- 假设较大整数:
一个非常大的哈希表。如果您有一个合适的值分布，通常的模数哈希函数将是合适的，如果没有，您可能希望将32位策略与哈希查找相结合。