How to find where does Point lies in given list of rectangles ? (In less than O(n) complexity)

The problem statement bit related to this one.

There is a list of rectangles that has 2 points given.

Each Rectangle is represented by x0,y0,x1,y1.

1. x0,y0 - Represents top left or starting point
2. x1,y1 - Represents bottom right or ending point

Note: We can sort the list in any format. Assume (can be changed) the list is sorted based on starting point.

Need to find given best rectangle where point X,Y lies in completely.

If more than one rectangle is overlapping, one can choose the rectangle with the smallest area.

This can be improved later to the shortest distance from any rectangle corner.

Input:

Point: (X, Y) = (1450,380)

List of rectangles :

[
  {
    "x0": 1797,
    "x1": 1854,
    "y0": 333,
    "y1": 434
  },
  {
    "x0": 1671,
    "x1": 1688,
    "y0": 423,
    "y1": 434
  },
  {
    "x0": 1565,
    "x1": 1594,
    "y0": 366,
    "y1": 378
  },
  {
    "x0": 1547,
    "x1": 1552,
    "y0": 112,
    "y1": 146
  },
  {
    "x0": 1439,
    "x1": 1457,
    "y0": 373,
    "y1": 396
  }
]

Output:

  {
    "x0": 1439,
    "x1": 1457,
    "y0": 373,
    "y1": 396
  }

One simple way to find is to iterate through all rectangles and find the smallest rectangle where the point lies. This is possible O(n) in complexity.

Is there a better solution for getting the best rectangle resolving overlapping scenarios in less complexity than O(n)?

A binary search won't work because you can only partition on one axis, but a spatial partitioning algorithm should work. For example, a quadtree data structure can trivially reduce the complexity of your search to O(logn) in a non-degenerate success case.

One can easily build a degenerate case that requires a linear scan however, where you have all elements of your array as the same rectangle. It's really up to how your data is coming in and how pedantic you want to be with labels.