Search a 2D Matrix — Step-by-Step Visualization

Algorithm Pattern

Binary Search

Key Idea

Because of the matrix's sorted properties, it can be visualized as a single 1D sorted array. We can use a standard binary search but map the 1D index back to 2D coordinates using row = index // cols and col = index % cols.

Step-by-Step Approach

1. Define the search range: low = 0, high = (rows * cols) - 1.
2. Calculate mid = (low + high) // 2.
3. Calculate the 2D position: r = mid // cols, c = mid % cols.
4. Compare matrix[r][c] with the target.
5. Adjust 'low' or 'high' based on the result and repeat until found or range is empty.

Common Gotchas

• Ensure integer division for row calculation: Math.floor(mid / cols).
• The O(log(rows * cols)) time complexity is achieved by binary search on all elements.