No replies to this topic

[gattu]

Hi,

I have a code where I need to search in a set of non-overlapping intervals, lets say { (1-10), (20-25), (30-40) } is my set. I need to search for a particular item, say 22, and determine which interval it lies in, (20-25) for this example.

I need to do this fast, as I have a large number of lookups. I am using a splay tree (basically a binary search tree which brings last accessed node to the root, to make searching tree fast). I was wondering if there was some way I could go down to O(1) using hash tables. But I can't figure out how I could hash intervals.

Any ideas?

~gattu~