Editorial: Search a Sorted 2D Matrix

by admin · Oct. 18, 2026

1 Intuition

Read row by row, the matrix is one sorted array.

2 Approach

Binary search over indices 0..rows·cols−1 and map index k to (k // cols, k % cols).

3 Complexity Analysis

Time O(log(rows·cols)), Space O(1).

4 Solution Code

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        rows, cols = len(matrix), len(matrix[0])
        lo, hi = 0, rows * cols - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            v = matrix[mid // cols][mid % cols]
            if v == target:
                return True
            if v < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return False

5 Code Walkthrough

The reference solution below implements the approach step by step.