Search in 2D Matrix (Advanced Problems)

1. Introduction

What is 2D Matrix Binary Search?

2D Matrix Binary Search applies standard binary search logic to multi-dimensional grids. By converting a flat 1D search index into 2D row/column coordinates, we can search a sorted matrix in logarithmic O(log(M × N)) time.

Why is it Important?

Instead of searching row-by-row (which takes O(M log N) or linear O(M + N) time), coordinate translation lets us treat the entire matrix as one giant sorted array. This achieves the absolute mathematical minimum complexity for searching a sorted grid.

Where is it Used?

Graphics Framebuffers: Locating pixels by linear offset addresses.

Geospatial Indexes: Finding coordinates in grid-based maps.

---

2. Mental Model: Unrolling the Matrix

Imagine a 2D grid of size 3 x 4 (3 rows, 4 columns) containing sorted numbers. If you slice the grid between rows and place them end-to-end, you get a single flat list of 12 elements:

To find the element at index 6 in the flat list, we convert it back to 2D coordinates using the column count (N = 4):

Row = 6 / 4 = 1

Col = 6 \% 4 = 2

Value = grid[1][2] = 16.

---

3. Core Concepts & Implementations

Virtual 1D Coordinate Translation

For a matrix with M rows and N columns:

Total search elements L = M × N.

Initial boundaries: lo = 0, hi = L - 1.

For any flat index mid, the 2D matrix cell is:

---

4. Visual Trace: Finding Target = 16 in a 3x4 Matrix

---

5. Real-World Applications

Relational Databases Page-Indexing: PostgreSQL/MySQL store database rows in fixed-size blocks (pages). Locating a record within a page's row index array uses coordinate mapping offsets.

Image Convolution & Filters: Locating source pixels by single-dimensional pixel array offsets in GPU shaders.

---

6. Interview Perspective

How Interviewers Ask This Topic

Interviewers test index arithmetic:

"Given a sorted 2D matrix, check if a target value exists." (LeetCode 74).

"Given a matrix where each row and column is sorted, find target." (LeetCode 240 -> uses a staircase search from top-right corner in O(M + N) time, instead of binary search).

Common Mistakes

> 2. Empty Grid Boundary Failure: Forgetting to check if the matrix or its first row is empty, which can cause divide-by-zero errors (mid / 0).

---

7. Summary

Total Range: Flat index range is 0 to (m * n) - 1.

Coordinate Conversion: row = mid / n, col = mid % n. Always divide and modulo by the column count n.

Time Complexity: O(log(M × N)) \approx O(log M + log N). Space complexity is O(1).

---

8. Quiz

Question 1: Why do we divide by n (columns count) instead of m (rows count) to get the row index?

Answer: Because each row contains exactly N elements. Slicing the matrix row-by-row means that every group of N sequential flat indices represents one full row. Thus, dividing the flat index by N tells us how many rows have been completed.

Question 2: What is the time complexity of searching a 1000 x 1000 sorted matrix using coordinate mapping?

Answer: O(log(10^6)) \approx 20 comparisons.

Question 3: If only the individual rows are sorted, but the first element of row i+1 is not greater than the last of row i, can you use virtual 1D binary search?

Answer: No. The entire unrolled list must be fully monotonic (sorted) for 1D mapping to work. If there are overlaps between rows, you must instead binary search each row individually in O(M log N) or use other search techniques.

Question 4: What is the C++ equivalent algorithm to search a flat vector?

Answer: std::binary_search().

Question 5: What is the row and column coordinate for index 14 in a matrix with 5 columns?

Answer: row = 14 / 5 = 2, col = 14 % 5 = 4. Coordinate is [2][4].