爲範圍匹配查找

Question

數據結構假設我有範圍的結構，以及它們的相關聯的數據，例如：

data [ 
    [ [0, 100], "New York"], 
    [ [101, 200], "Boston"], 
    ... 
] 

對於接收N作爲參數並返回其中N是在輸入的函數左側元素的範圍。

例如，

> 103 
< "Boston" 

會有什麼轉變以上，以達到最快的查找時間的最佳結構？

Answer 1

如果您的數據集應該是動態的，請使用interval tree。

Answer 2

我建議你試試B +樹。因爲我還沒有親自嘗試過這個問題。 B +樹可以將數組作爲其子，因此您可以將索引0-100的數據值設置爲紐約，101指向樹中的子2。

檢查有關B +樹here

我會建議你採取定期的辦法對於這一點，櫃面你的數據很小。