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

解题思路参考题解区漫漫云天自翱翔

由于行列递增，可以得出：

a.在一列中的某个数字，其上的数字都比它小

b.在一行中的某个数字，其右的数字都比它大

搜索流程：

a.首先从数组左下角搜索.

b.如果当前数字大于target,那么查找往上移一位,如果当前数字小于target,那么查找往右移一位。

c.查找到target,返回true; 如果越界，返回false。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param target int整型 
# @param array int整型二维数组 
# @return bool布尔型
#
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        #特殊情况
        if array==[[]]:
            return False
        
        row=len(array)#总行数
        col=len(array[0])#总列数
        #左下角的坐标
        i=row-1
        j=0
        while array[i][j]!=target:
            if array[i][j]>target:
                i=i-1
            else:
                j=j+1
            
            if i==-1 or j==col:#搜索到边界了
                return False
        return True 

时间复杂度:O(M+N)

空间复杂度:O(1)

另外，还有双二分查找的思路。 利用数组行列递增特性。一维的二分查找可以舍弃一半的查找范围，二维的二分可以舍弃左上部分或者右下部分1/4的查找范围。

时间复杂度:O(logM*logN)

空间复杂度:O(1)