CODEWITHSUNDEEP
jsonalgorithmdata-structures
Tzury Bar Yochay
Tzury Bar Yochay

Reputation: 9004

Data Structure for Range Matching Lookup

Assume I have a structure of ranges, and their associated data, for instance:

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

For a function that receives a N as an arguments and returns the entry where N is in the range of the left element.

for instance, 

> 103
< "Boston"

What will be the best structure to transform the above to achieve the fastest lookup time?

Upvotes: 1

Views: 118

Answers (2)

Ashik Vetrivelu
Ashik Vetrivelu

Reputation: 1041

I would suggest you to try with B+ tree. As I haven't personally tried this problem either. B+ tree can have array as its child so you could set the data value for index 0-100 as New York with 101 pointing to child 2 in the tree.

Check about B+ tree here

I would recommend you to take regular approach for this, incase your data is small.

Upvotes: 1

MBo
MBo

Reputation: 80187

If your data set should be dynamic, use interval tree.

Upvotes: 3

Related Questions