题解 | #二维数组中的查找#

解题思路：首先选取数组右上角的数字。如果该数字等于要查找的数字，则查找过程结束，返回True；如果该数字大于要查找的数字，则剔除这个数字所在的列；如果该数字小于要查找的数字，则剔除这个数字所在的行。也就是说，如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围内剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找的范围为空。

时间复杂度：O(m+n)，m为行数，n为列数，最坏的情况下是m+n;

空间复杂度：O(1)

基于python3实现：

class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        found = False
        row = 0
        column = len(array[0]) -1
        # row, column对应的时矩阵右上角的元素
        # while循环的条件，row往下走不超过array的行数，column往左走不低于0
        while row < len(array) and column >= 0:
            # 如果右上角的元素与target相等，则返回true
            if array[row][column] == target:
                found = True
                break
            # 如果右上角元素大于target，则剔除所在的列
            elif array[row][column] > target:
                column-=1
            # 如果右上角元素小于target，则剔除所在的行
            else:
                row+=1
        return found

其它解题思路：

1. 暴力破解，遍历数组，查找是否存在target，时间复杂度O(mn);

2. 因为行列有序，所以对数组的每一行进行二分查找，时间复杂度O(mlogn)；