标签:二分法

解题思路参考:

https://blog.nowcoder.net/n/3fbe666d7ee443c8b4e957369e960e15

具体做法:

  • step 1:首先获取矩阵的两个边长,判断特殊情况。
  • step 2:首先以左下角为起点,若是它小于目标元素,则往右移动去找大的,若是他大于目标元素,则往上移动去找小的。
  • step 3:若是移动到了矩阵边界也没找到,说明矩阵中不存在目标值。

代码实现:

class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        if len(array) == 0:
            return False
        if len(array[0]) == 0 or len(array[-1]) == 0:
            return False
        
        n = len(array)  # n个子数组
        m = len(array[0])  # 每个子数组有m个元素
        i = n - 1
        j = 0
        while i >= 0 and j < m:
            # 如果target更小,缩小行数
            if array[i][j] > target:
                i -= 1
            # 如果target更大,增大列数
            elif array[i][j] < target:
                j += 1
            else:
                return True
        # 跳出while循环前,如果未返回True,则说明未匹配到target值,返回False
        return False