range / interval query algorithm

Question

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.

Answer 1

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.