Search in 2D Matrix

The Efficient Grid Search

Searching through a massive grid can be slow ($O(N cdot M)$). However, if the grid is "perfectly sorted"—where each row is sorted and its first element is greater than the previous row's last—we can treat the entire grid as one long sorted line. This allows us to use Binary Search to find any value instantly.

The Assignment

Your mission is to find the target in the sorted grid. Your function receives a matrix and a target value.

1. Treat the matrix as a flattened array where the total length is rows * cols.
2. Use Binary Search logic with low = 0 and high = length - 1.
3. To find the grid coordinates from a "flat" index:
   • row = Math.floor(index / cols)
   • col = index % cols
4. Print true if the target exists, otherwise print false.