240. Search a 2D Matrix II

LeetCode - The World's Leading Online Programming Learning PlatformLeetCode

自右上而左下 Binary Search

74. Search a 2D Matrix

1. 跟 Q74 不同，这次的升序只在各行和各列内部，无法再把 matrix 当作一维sorted array处理。

2. 如果从左上角开始搜索，由于元素升序为自左向右和自上而下，因此如果 target 大于当前搜索元素时还有两个方向需要搜索，不太合适。

3. 如果从右上角开始搜索，当前行与当前列连接起来就是一个sorted array，这样就可以利用二分法的思路，通过比较当前元素与target ，排除一列或者一行元素（大于当前元素则排除当前行，小于当前元素则排除当前列，由矩阵特点可知）。

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or not matrix[0]: return False
        m, n = len(matrix), len(matrix[0])
        if matrix[m-1][n-1] < target or matrix[0][0] > target: return False
        row, column = 0, n-1
        while row < m and column >= 0:
            cur = matrix[row][column]
            #print(cur)
            if cur == target: return True
            elif cur > target: column -= 1
            else: row +=1
                
        return False