难度: Medium
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 输出：true
示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 输出：false
提示：
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300-109 <= matrix[i][j] <= 109-109 <= target <= 109运行时间: 120 ms
内存: 22.1 MB
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
#记录矩阵的行列数
i, j = len(matrix)-1, 0
F = False
while i >= 0 and j < len(matrix[0]):
flag = matrix[i][j]
if flag == target:
F = True
break
elif flag < target:
j += 1
else:
i -= 1
print(i ,j)
return F
这个题解采用了一种巧妙的搜索方式。从矩阵的右上角开始搜索，如果当前元素等于目标值，则找到目标值，直接返回 true。如果当前元素大于目标值，由于当前元素已经是该列最小的元素，因此将搜索范围缩小到当前元素的左边一列。如果当前元素小于目标值，由于当前元素已经是该行最大的元素，因此将搜索范围缩小到当前元素的下面一行。通过不断缩小搜索范围，最终可以确定目标值是否存在于矩阵中。
时间复杂度: O(m+n)
空间复杂度: O(1)
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
# 记录矩阵的行数和列数
m, n = len(matrix), len(matrix[0])
# 初始化行索引为最后一行，列索引为第一列
i, j = m - 1, 0
# 初始化找到目标值的标志为 False
found = False
# 当行索引大于等于0且列索引小于列数时循环
while i >= 0 and j < n:
# 获取当前元素
curr = matrix[i][j]
# 如果当前元素等于目标值，将找到目标值的标志设为 True，并退出循环
if curr == target:
found = True
break
# 如果当前元素小于目标值，将列索引加1，缩小搜索范围到下一列
elif curr < target:
j += 1
# 如果当前元素大于目标值，将行索引减1，缩小搜索范围到上一行
else:
i -= 1
# 返回是否找到目标值
return found
从右上角开始搜索具有独特的优势，它允许我们在每一步决策中只有两个选择：向左或向下。这种搜索方式利用了矩阵的有序性质：每行从左到右递增，每列从上到下递增。从右上角开始，如果当前元素大于目标值，只能向左移动（因为向下所有值都将更大），如果当前元素小于目标值，只能向下移动（因为向左所有值都将更小）。相比之下，从左上角、左下角或右下角开始将不具有这种一致的决策路径，因为它们会在搜索过程中同时存在向两个方向移动的可能性，这将增加算法的复杂度。
当当前元素大于目标值时，由于每列从上到下是递增的，位于当前元素下方的所有元素都将大于当前元素，因此它们也必然大于目标值。这意味着向下查找将不可能找到较小的、等于目标值的元素。因此，我们可以安全地排除当前元素所在的列，将搜索范围移至左边的列，减少搜索空间。
是的，算法的有效性基于矩阵的每列都是严格递增的这一前提。由于每列从上到下递增，当前元素小于目标值时，只有向下移动可能找到更大的元素，而当前行中位于当前元素右侧的所有元素都大于当前元素，但不一定达到目标值。因此，搜索向下移动是为了在递增的列中寻找可能等于目标值的更大元素。
如果矩阵为空或包含空的行或列，算法需要对这些特殊情况进行处理以避免运行时错误。算法中的初始条件检查矩阵的行数和列数，但并没有明确检查是否有空的行或列。在实际应用中，应该在算法开始前添加检查，确保矩阵不为空且所有行和列都有效，从而确保算法的稳定运行并防止例如越界等错误。