Search a 2D Matrix

How it works

Because the matrix is sorted row-wise and each row is sorted left-to-right, the entire matrix behaves like one big sorted array. If we imagine flattening the matrix into a single list, the order of elements doesn't change.

This means we can run one binary search from index 0 to ROWS * COLS - 1. For any mid index m, we can map it back to the matrix using:

• row = m // COLS
• col = m % COLS

This lets us access the correct matrix element without actually flattening the matrix.

Steps

1. Treat the matrix as a single sorted array of size ROWS * COLS.
2. Set l = 0 and r = ROWS * COLS - 1.
3. While l <= r:
   • Compute the middle index m = (l + r) // 2.
   • Convert m back to matrix coordinates:
     • row = m // COLS
     • col = m % COLS
   • Compare matrix[row][col] with the target:
     • If equal → return true.
     • If the value is smaller → search the right half (l = m + 1).
     • If larger → search the left half (r = m - 1).
4. If the loop ends with no match, return false.

Complexity

• Time complexity: O(log(m * n))
• Space complexity: O(1)

Where m is the number of rows and n is the number of columns of matrix.

Things to watch for

Confusing Row vs Column Indexing

When converting a 1D index to 2D coordinates in the one-pass binary search approach, it is easy to mix up row = m // COLS and col = m % COLS. Using ROWS instead of COLS in these formulas will produce incorrect indices and lead to wrong answers or out-of-bounds errors.

Off-by-One Errors in Row Selection

In the two-pass binary search approach, after identifying the candidate row, forgetting to recalculate row = (top + bot) // 2 before the second binary search can cause you to search in the wrong row. Similarly, checking top <= bot incorrectly after the first loop can lead to false negatives.

Not Handling Empty Matrix

Failing to check if the matrix is empty or if any row is empty before accessing matrix[0] will cause runtime errors. Always validate that both ROWS > 0 and COLS > 0 before proceeding with the search.

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        ROWS, COLS = len(matrix), len(matrix[0])

        l, r = 0, ROWS * COLS - 1
        while l <= r:
            m = l + (r - l) // 2
            row, col = m // COLS, m % COLS
            if target > matrix[row][col]:
                l = m + 1
            elif target < matrix[row][col]:
                r = m - 1
            else:
                return True
        return False

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int ROWS = matrix.size(), COLS = matrix[0].size();

        int l = 0, r = ROWS * COLS - 1;
        while (l <= r) {
            int m = l + (r - l) / 2;
            int row = m / COLS, col = m % COLS;
            if (target > matrix[row][col]) {
                l = m + 1;
            } else if (target < matrix[row][col]) {
                r = m - 1;
            } else {
                return true;
            }
        }
        return false;
    }
};