You can probably recast your problem into a 1D multiple particle collisions problem.
Each interval is represented by a particle of radius half the interval, positioned at the middle of the interval.
Because the radius vary, you can either use adaptive algorithm, or split the interval into multiple small particles.
There is not a lot to gain when doing a single query, but when you are batching queries, you can share the computation and memory accesses. Using radix sort for sorting the integers you get a complexity for iterating over all collisions of O( NbKeys + NbQueries + NbCollisions ).
Comments
You can probably recast your problem into a 1D multiple particle collisions problem.
Each interval is represented by a particle of radius half the interval, positioned at the middle of the interval.
Because the radius vary, you can either use adaptive algorithm, or split the interval into multiple small particles.
There is not a lot to gain when doing a single query, but when you are batching queries, you can share the computation and memory accesses. Using radix sort for sorting the integers you get a complexity for iterating over all collisions of O( NbKeys + NbQueries + NbCollisions ).