# How can I efficiently find out if X is in any of N ranges of L-R numbers?

This is part of a bigger problem, which is to find out if point `XYZ` exists in any of `n` `(XYZ -> XYZ)` "boxes".

I'm currently splitting up the problem into a smaller one, by focusing on one dimension first and "filtering" till either a range is found, or it's not;

How can I find out if my number `X` is in any of `n` ranges with only a "beginning" and an "end" number?

PS: I've already found some suggestions like "interval trees" and "segment trees", but I couldn't quickly find out if that was what I needed or not.

The problem that you've posted is unclear in the following:

• Are you given one X and N ranges [L, R] or many X's for the same N ranges?
— This makes a big difference in efficiency considerations.
• Do you need to constantly modify the N ranges: adding/removing ranges, or adjusting L's and R's
— This also makes a huge difference in efficiency considerations
• Do you really just need to know if X is in any of the N ranges, or which of the N ranges?

Assuming then, that the ranges are constant and you want to look up many X's, you can precompute a data structure given the N ranges.

Depending on what you consider efficient, and on the total range of lowest L to highest R, you can either generate a total array or binary search array for the data structure, which goes to the how to index the array — direct indexing or binary search, respectively.

If you really only want to know whether X is in any of the ranges, the element type for the array is a boolean (yes/no), and for the binary search array, positions at range transitions and the boolean.

If you need to know which ranges X is an element of you might use a bit vector instead of a single boolean.

Still, this sounds like an XY problem.  It is difficult to generalize single dimensional solution to higher dimensions, so k-d trees or one of the many variants are probably be indicated.