240. 搜索二维矩阵 II

**搜索二维矩阵 II**

在前面的文章中，我们讨论了如何在一个排序的二维矩阵中查找一个目标值。然而，这个问题并没有解决一个更复杂的问题：如果我们不能保证矩阵是排序的，那么我们该怎么办？这个问题就是本文要解决的。

**问题描述**

给定一个二维整数矩阵 `matrix` 和一个目标值 `target`，请写一个函数来判断是否存在目标值在矩阵中。矩阵可能包含重复的元素。

**示例**

* 输入：`matrix = [[1,3,5],[7,9,11],[13,15,17]]`, `target =12`
输出：`False`

* 输入：`matrix = [[1,3,5],[7,9,11],[13,15,17]]`, `target =18`
输出：`False`

**解决方案**

我们可以使用二分查找来解决这个问题。然而，这个方法需要矩阵是排序的，我们不能保证这一点。

因此，我们需要找到一个更通用的方法。我们可以先找到矩阵中最小和最大值，然后使用二分查找来找到目标值。

**代码**

class Solution:
 def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
 # 如果矩阵为空，则返回 False if not matrix or not matrix[0]:
 return False # 找到矩阵中最小和最大值 min_val = matrix[0][0]
 max_val = matrix[-1][-1]
 # 如果目标值不在矩阵的范围内，则返回 False if target < min_val or target > max_val:
 return False # 使用二分查找来找到目标值 low, high =0, len(matrix) * len(matrix[0]) -1 while low <= high:
 mid = (low + high) //2 num = self.find_num(matrix, mid)
 # 如果找到目标值，则返回 True if num == target:
 return True # 如果目标值小于当前值，则更新高位指针 elif num > target:
 high = mid -1 # 如果目标值大于当前值，则更新低位指针 else:
 low = mid +1 # 如果找不到目标值，则返回 False return False def find_num(self, matrix, index):
 # 找到矩阵中第 index 个数字的位置 row = index // len(matrix[0])
 col = index % len(matrix[0])
 # 返回第 index 个数字 return matrix[row][col]