通過浮點或雙字段算法進行索引

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，範圍要求。