74. Search a 2D Matrix

Loading...LeetCode

题目给的matrix是排序过的，可以当作一维 sorted array 处理，直接binary search 模版。

class Solution:
    def searchMatrix(self, 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+1 < r:
            mid = (l+r)//2
            v_mid = matrix[mid//n][mid%n]
            print(v_mid)
            if v_mid == target:
                return True
            elif v_mid > target:
                r = mid
            else:
                l = mid
        
        return matrix[l//n][l%n] == target or matrix[r//n][r%n] == target