Search a 2D Matrix

Problem Id: 74 Difficulty: Medium Tag: Array Tag: Binary Search


Intuition

This problem is based on binary search on a 1D array. The equally length of this matrix is m * n. And each position x, y could be converted to 1D index to n * x + y.

Solution


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix:
            return False
        elif not matrix[0]:
            return False

        if matrix[0][0] > target:
            return False

        m, n = len(matrix), len(matrix[0])
        lo, hi = 0, m * n
        while hi - lo > 1:
            mid = (lo + hi) // 2
            value = matrix[mid // n][mid % n]
            if value <= target:
                lo = mid
            else:
                hi = mid
        return matrix[lo // n][lo % n] == target