通过浮点或双字段算法进行索引

Question

我有一项任务，可以通过某些对象的字段在对象的巨大内存数组中执行快速搜索。我需要选择符合某些标准的对象的子集。

可以将标准指定为浮点值或这些值的范围（例如，2.5..10）。

问题是要搜索的浮点属性分布不均匀;它可以包含数值范围为10-20（例如）的少数对象，以及值为0-1的另一百万个对象，以及值为100-150的另一百万个对象。

那么，如何构建索引以有效搜索这些对象呢？代码示例是受欢迎的。

Answer 1

我看不出有什么值的分布与建立索引（与确切的重复可能是个例外）做。由于数据适合内存，只需提取所有字段的原始位置，对它们进行排序，然后使用@MattiLyra建议的二进制搜索。

我们错过了什么吗？

Answer 2

如果内存数组是有序的，那么二进制搜索将是我的第一次尝试。维基百科条目也有示例代码。

http://en.wikipedia.org/wiki/Binary_search_algorithm

Answer 3

如果您只查找查询，则进行一次排序，然后进行多个二进制搜索即可。

如果您想要最终的查找速度和更多，您也可以尝试一个完美的哈希算法。

如果您不仅需要查找，还可以查看treaps和红黑树。前者平均速度很快，而后者是体面的表现者，手术持续时间变化较小。

Answer 4

您可以尝试一个range tree，范围要求。