[Math] is it possible to hash a range

algorithmsfunctionshash function

OK. I am not a math guy. I'm a programmer, so forgive me for the non-math lingo.

let's say I have 3 ranges

[1 - 3]    //  index 0
[4 - 6]    //  index 1
[7 - 13]   //  index 2
etc etc etc with any arbitrary sorted, non-overlapping range

Is it mathematically possible to do something like this?:

func(2) -> should print result index[0]

or

func(8) -> should print result index[2]

The idea is that I want to provide any arbitrary sorted range and store it as a hash. The are no overlapping ranges.

Then provide a number to the func and it should tell me the index.

In order to do this, I think i would need to (for example the first range), take the numbers 1, 2, 3 and convert it into a hash. So that if an input of say 2 was provided, it would map to that exact hash.

Is this possible?

[Please me me with the correct tags for the question.. i do not know which area of maths this falls under.]

Edit : Range count can be any amount. I am trying to avoid looping. Count can reach as high as 60k. That's why i was wondering if hashing was possible with mathematics given the requirements above. If it is possible in maths, then it will be possible in code.

Edit #2: My attempt to make the question more math like.. i hope.

Is it possible to take a list of sorted integers: lets say 5 => [1, 2, 3, 4, 5]
And create a hash with them, such that the following is possible.

func(0) results false
func(6) results false
func(1) results true
func(2) results true
func(3) results true
func(4) results true
func(5) results true

Best Answer

If you know the 'index' values for each range, I'm guessing you've got an array holding those ranges in order. Why not do a boring-old bisection search (comparing the value you want to look up against the 'start' values of each range) to find the range with the largest 'start' value less than the value you're looking up. As that's the only possible range that could contain your value you just have to check if your value is less than that range's 'end' value and either return that range's index or "No Range Found".

Re-reading your question, you don't actually want the 'index position' returned, you want the Range object. (I'm assuming you've got some kind of object that represents a range.) So, 

func(2) -> 0

isn't what you want, but 

func(2) -> Range(1,3)

is. In that case you can ignore what I said about returning indexes, and just return the Range() object. But this does still assume that you've got your Ranges stored in a sorted array.

Related Question