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.