字典樣式查找數百萬個對應於一組值的鍵？

Question

我有很多指數。

有對應於索引範圍

例如特定的一組：給定一個特定的索引

Range  Group 

0-100  A 
101-220  B 
221-543  C 
...  ... 
3K-40K  DF 

我需要一種方法來查找一個相應的基團，。 例如，我需要一個方法：

(Group)groupForIndex:(index) 

所以，如果我叫groupForIndex:(115)，其結果必然是B

我正在尋找，以改善我現在有辦法。

我不會只使用一個NSDictionary（或地圖），因爲這將是每個ID的條目，可能是數百萬，並且會浪費空間，因爲許多鍵具有相同的值。我決定使用數組和字典的組合。 對於每個「上限」，將有所述陣列中的條目

實施例：

[0] = 100 
[1] = 220 
[2] = 543 

並且對於每個上限，就會出現在詞典

Key   Value 
100    A 
220    B 
543    C 

的條目這樣，使用二進制搜索，給定索引我可以查找一個上限。一旦我有了上限，我就有了字典的鑰匙。

這是我能想出的最有效的查找方案。什麼是更有效的方式來做到這一點？

Answer 1

在（排序）數組中的二進制搜索速度非常快，所以如果組和索引是固定的，那麼您的方法對我來說看起來不錯，因此數組必須只構建一次（或者與偶數相比查找）。

如果組的組集合經常變化，則不同的數據結構（例如某些 樹）可能更適合，而不是在每次更改時重建陣列。

正如我在評論說，我將取代字典由（與第一個相同大小的）另一個陣列

[0] = "A" 
[1] = "B" 
[2] = "C" 
... 

，然後只映射所述第一陣列中找到的索引經由第二陣列對應的羣組 。

由於每個組的「上限」不存儲在兩個地方，這可能會稍微快一些，並且可能更容易維護。