Q47: Search a 2D Matrix. - DSA Patterns (Multi-Lang)

In Simple Words: Treat $M \times N$ matrix as a single 1D virtual sorted array of size $M \cdot N$. Coordinate translation: row = Math.floor(mid / N), col = mid % N.

Time: $O(\log(M \cdot N))$ | Space: $O(1)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def searchMatrix(matrix: list[list[int]], target: int) -> bool:
    if not matrix or not matrix[0]: return False
    m, n = len(matrix), len(matrix[0])
    l, r = 0, m * n - 1
    while l <= r:
        mid = l + (r - l) // 2
        val = matrix[mid // n][mid % n]
        if val == target:
            return True
        elif val < target:
            l = mid + 1
        else:
            r = mid - 1
    return False