标签:二分法
解题思路参考:
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