(数组与矩阵) 剑指 Offer 04. 二维数组中的查找 ——【Leetcode每日一题】

**剑指 Offer04. 二维数组中的查找**

**问题描述**

在一个二维数组中，找到一个给定的目标值。该二维数组由若干行组成，每行又由若干列组成。

**示例**

输入：`[[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]]`

目标值：`5`

输出：`True`

**解决方案**

我们可以使用二分查找的思想来解决这个问题。具体来说，我们可以先找到目标值所在行，然后再在该行中进行二分查找。

class Solution:
 def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
 # 如果矩阵为空，则直接返回False if not matrix or not matrix[0]:
 return False # 找到目标值所在行 row =0 while row < len(matrix) and matrix[row][0] <= target:
 row +=1 # 如果目标值不在矩阵中，则直接返回False if row == len(matrix):
 return False # 在目标值所在行进行二分查找 left, right =0, len(matrix[0]) -1 while left <= right:
 mid = (left + right) //2 if matrix[row-1][mid] == target:
 return True elif matrix[row-1][mid] < target:
 left = mid +1 else:
 right = mid -1 # 如果目标值不在矩阵中，则直接返回False return False

**代码注释**

* `if not matrix or not matrix[0]:` 检查是否为空，避免异常。
* `row =0` 初始化行索引。
* `while row < len(matrix) and matrix[row][0] <= target:` 找到目标值所在行。
* `left, right =0, len(matrix[0]) -1` 初始化二分查找的左右边界。
* `while left <= right:` 在目标值所在行进行二分查找。
* `if matrix[row-1][mid] == target:` 检查是否找到目标值。

**时间复杂度**

* 找到目标值所在行：O(log n)，其中 n 是矩阵的行数。
* 在目标值所在行进行二分查找：O(log m)，其中 m 是矩阵中每行元素的数量。
* 总时间复杂度：O(log n + log m)。

**空间复杂度**

* 使用了常数个额外变量，因此空间复杂度为 O(1)。