Fastest way to find the smallest interval of a number
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.