# range / interval query algorithm

I've an hash (base 32 for what it's worth):

hash = 'ab352eghjhngd4'


And I've subscribers that want to listen to new hashes in a range.

   listener = { startAt: 'ab31', endAt: 'ab40', obj }
listener2 = { startAt: 'ab350', endAt: 'ab351', obj }


In this case listener1 should be notified of the new hash while listener2 shouldn't.

I'd like to find another algorithm than just iterating through all listeners to find if they fit.

I was thinking of holding an array for startAt

startAtOrderedArray = [
{ startAt: 'ab31', endAt: 'ab40', obj },
{ startAt: 'ab350', endAt: 'ab351', obj },
{ startAt: 'uc', endAt: 'uc2', obj }
]


Then using binary search I can forget the third item because it's above the hash which was ab352eghjhngd4.

Then I can do the same with endAt.

endAtOrderedArray = [
{ startAt: 'uc', endAt: 'uc2', obj },
{ startAt: 'ab31', endAt: 'ab40', obj },
{ startAt: 'ab350', endAt: 'ab351', obj },
]


So I end up with:

 before = [
{ startAt: 'ab31', endAt: 'ab40', obj },
{ startAt: 'ab350', endAt: 'ab351', obj },
]

after = [
{ startAt: 'uc', endAt: 'uc2', obj },
{ startAt: 'ab31', endAt: 'ab40', obj },
]


So now if an item is in both array then it's interested in the hash.

The issue however is the complexity is still linear so I'm wondering how can I do better ?

I'd like the question to be as general as possible but for my specific use case it is likely that the first char of startAt and endAt are the same. So { startAt: 'ab', endAt: 'u23' } is not likely.

• Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– Raphael
Sep 13, 2017 at 5:31

Use an interval tree. It is designed to support exactly this. In particular, the query "find all ranges that contain this value" is known as a stabbing query, and it can be answered in essentially $O(\log n)$ time.