Hashing a range

Question

I have an array of range elements. Every element is has a start and an end. Within the array, the ranges are not overlapping, and they are sorted.

i.e. (code just to illustrate, do not expect it to compile):

var arr = { [0,3], [5,10], [15,59] };

Given a value (say 9), is there a hash function of the ranges that will allow me to quickly get the element that has the range that contains the value?

Of course there is the naive solution, just cycle though each element until you find the right one; the more elaborate one, like binary search by the start of the range; and the patented one of creating a binary tree with the ranges.

But does anybody knows of a way to use a hash?

Answer 1

You could precompute the nearest neigbour in advance and store it somewhere. In your example the table has 0..59 entries and you store the index of the nearest range at every index.

That way it will be really fast.

Answer 2

What about using a Dictionary<int, Element> to hold all numbers in all ranges, i. e. adding the four entries

0, [0,3]
1, [0,3]
2, [0,3]
3, [0,3]

and so on for the other ranges. It uses a hash by using the Dictionary, but I doubt it is the most efficient solution.

Answer 3

You could create an index for the start values to index in arr.

var arr = { [0,3], [5,10], [15,59] };

var dictStart = new Dictionary<int, int>();
dictStart.Add(0, 0);
dictStart.Add(5, 1);
dictStart.Add(15, 2);

Now to get the range you can do a binary search on the values of the dictStart dict for the first element that is higher that the value to search for. Then take the previous entry.

Difficult to explain. As an example look up 9. Do the search what got element e=[5, 1].

var range = arr[e[1]];   // = [5, 10]
bool isWithin = val <= range[1] && val >= range[0];

So that way it will be less memory invasive. The key is to have a fast search fro the start values of the ranges.

I guess it will solve the problem but it is not a hash.