Fastest way to find the smallest interval of a number

Question

Here is my problem : Given a range, let's say 0 to 10.000, and some numbers in that range (like 23, 1456, 280, 3586), I want to find, for any input x, the two closest numbers to x, the smaller one the greater one. For example for x=100, the two numbers are 23 and 280, for x=350 they are 280 and 1456.

Is there a faster way to do that than a binary search on the list of numbers ? I vaguely remember the existence of a data structure for this task, but in my case the numbers are dynamic and will change during the execution of my algorithm.

Answer 1

The relevant phrase is ​ "predecessor search" .

For that, you can dynamically choose whether-or-not equality is allowed by

for each number in the range, storing 2 times that number rather than that number directly
and
for each actual query q, submitting ​ (2*q) ± 1 ​ instead of q,
where the sign depends on whether you want to allow equality
and
dividing by 2 before returning

.

With that, the greater one can be found using predecessor search in the negatives of
the actual numbers. ​ ​ ​ For your case, you could simply reverse the range, like storing
10000-23,10000-1456,10000-280,10000-3586 ​ rather than ​ 23,1456,280,3586 .


Page 6 of this pdf gives upper bounds for dynamic predecessor searching
and references for data structures achieving those bounds.

This pdf gives another data structure which does what you want and much more.