CODEWITHSUNDEEP
algorithmperformancesearchdata-structurestime-complexity
Aayush Taneja
Aayush Taneja

Reputation: 561

Best Data Structure for searching a coordinate in a 2D grid of categories

I want to search a coordinate in a 2D grid in which each element stores the horizontal and vertical coordinate limits and return a corresponding .

For Example: let the coordinate to be searched be (15,25) and the Grid be (where A,B,C,D,E and F are the return values): 

 (0,0) -  (0,10) - (0,20)  - (0,30)
   |   [A]  |  [B]   |  [C]   |
(10,0) - (10,10) - (10,20) - (10,30)
   |   [D]  |  [E]   |  [F]   |
(20,0) - (20,10) - (20,20) - (20,30)
   |   [G]  |  [H]   |  [I]   |
(30,0) - (30,10) - (30,20) - (30,30)

So, as our coordinate(15,25) is between 10-20 Vertically and 20-30 Horizontally, The search function should return [F].

So what data structure and searching algorithm would be the best in terms of complexity in such a case?

NOTE: The Coordinate limits of both horizontal and vertical axes are already sorted in increasing order.

Upvotes: 3

Views: 1740

Answers (2)

gsamaras
gsamaras

Reputation: 73444

what data structure?

Array.

An array, with an element being a 2D point for example. This will be O(n), wheren` is the size of your axis.

searching algorithm? [..] data are already sorted in increasing order.

Use Binary Search.

Twice, one for every axis, which will keep the asymptotic notation at O(logn).

Of course, you would have to stop searching when you meet 20 (in case the query is 15), since it might be that the query is not present in the array. so you want to stop searching if the current element is greater or equal to the query.

PS: If the grid is not square, then use a kd-tree and search for the Nearest Neighbor.

Upvotes: 2

High Performance Mark
High Performance Mark

Reputation: 78364

Ignore, for the time being, the coordinates you are actually using on your grid and label them 0,1,2,3,... along each axis. Now you have a nice plain array.

Next, figure out the function to transform an actual coordinate to the pseudo-coordinates defined in the previous step. In your example this function is simply integer (or truncating) division by 10. You'll need to be a bit careful, when the coordinates aren't so nicely spaced, to ensure that the function finds the pseudo-coordinate of the (as you've drawn it) top-left corner of the cell.

Now you have to make two function calls and one lookup into an array. The complexity of this depends on the complexity of the function you have to write to translate from coordinates to pseudo-coordinates, but I struggle to see how that is going to be much more than O(k) for some small integer value of k. And looking up an element in an array is O(1).

Upvotes: 2

Related Questions