Assume we have large list of pairs:
struct {x: double, y: double} pair;
vector<pair>
What is the most effective way to find all pairs where (x1 < x < x2) AND (y1 < y < y2)?
O(n) is not acceptable, sorting by one variable and scanning another does not look good too.
Preprocessing is acceptable so trading additional memory for performance is OK
1
What you are looking for is called a Spatial Index.
In your case, you are looking for simplest case of getting all 2D points inside a rectangle. Even simple quad tree should be great improvement if you have lots of points.
The problem of those kind of indexing algorithms and structures is that they are highly dependent of shape of the data. While they all have nice theoretical complexity, it would be best if you invested some time into trying different algorithms, so you find one that best fits your real-world data.
0
I’m assuming you want low amortized cost, i.e. preprocessing is acceptable.
You’re trying to find a data item with specific property. Don’t be misled by the fact that the property is expressed as four different numeric comparisons. It’s really a property of the entire item. That means you need to sort your data according to a measure that takes all conditions into account and then search for the combined measure first.
In this instance, looking for a pair with 10 < x < 12 and 3 < y < 5 means looking for a pair where 13 < x+y < 17. You could just sort your list of pairs y their sum and quickly find all candidates that satisfy the combined condition.
Not all of them satisfy the individual conditions, but you can define a secondary sort criterion that takes e.g. the x value into account. This is often good enough that you can get by with the standard sorting an earching algorithms, without defining task-specific two-dimensional linked data structures.
(Note that whether that’s fast enough for your purposes depends on what your purposes are. It’s entirely possible that you do need more complicated preprocessing to meet your business goal. But in general I think it’s often better to tweak existing, simple algorithms than to introduce a task-specific one, if only because standard library sorts and searches are likely to be tuned much better than you could do it yourself.)
1