74. 搜索二维矩阵

https://leetcode-cn.com/problems/search-a-2d-matrix/

解法一:

通过坐标变换,将二维矩阵视为一维。由于是有序的,因此一维上依然是有序的。

n * m matrix convert to an array => matrix[x][y] => a[x * m + y]

an array convert to n * m matrix => a[x] =>matrix[x / m][x % m]

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        n = len(matrix)
        if n == 0:  #排除边界情况
            return False
        m = len(matrix[0])
        if m == 0:
            return False
        l, h = 0, m * n - 1  #左右起点
        #二分
        while l <= h:
            mid = (l + h) // 2  #中点
            if matrix[mid // m][mid % m] < target:
                l = mid + 1
            elif matrix[mid // m][mid % m] > target:
                h = mid - 1
            else:  #mid找到
                break
        return matrix[mid // m][mid % m] == target

最后更新于