【二分查找】——搜索二维矩阵#力扣hot100

有序——>原地二分！

74. 搜索二维矩阵

一、问题描述

给你一个满足下述两条属性的 m x n 整数矩阵：

1. 每行中的整数从左到右按非严格递增顺序排列。
2. 每行的第一个整数大于前一行的最后一个整数。

现在给你一个整数 target，如果 target 在矩阵中，返回 true；否则，返回 false。

二、示例说明

1. 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]，target = 3，输出：true。
   • 在给定的矩阵中，目标值3存在于第一行。
2. 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]，target = 13，输出：false。
   • 目标值13不在给定的矩阵中。

三、提示信息

1. m == matrix.length：矩阵的行数。
2. n == matrix[i].length：矩阵的列数。
3. 1 <= m, n <= 100：矩阵的行数和列数的范围。
4. -104 <= matrix[i][j], target <= 104：矩阵中的元素和目标值的取值范围。

四、解题思路

1. 首先，可以将这个二维矩阵看作是一个一维数组，利用矩阵的性质，我们可以通过简单的计算来确定目标值在这个一维数组中的位置范围。
2. 然后，使用二分查找算法在这个范围内查找目标值。

五、代码实现

以下是使用 Python 实现的代码：

def searchMatrix(matrix, target):m = len(matrix)n = len(matrix[0])left = 0right = m * n - 1while left <= right:mid = left + (right - left) // 2row = mid // ncol = mid % nif matrix[row][col] == target:return Trueelif matrix[row][col] < target:left = mid + 1else:right = mid - 1return False

第二种写法：

class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:# 二分查找# 需要将一维数组的索引转换为二维矩阵的行和列索引。# 获取矩阵维度m = len(matrix)     # 行n = len(matrix[0])  # 列# 定义一维数组的左右指针left = 0right = m * n -1# 闭区间形式while left <= right:mid = (left + right) // 2# 将一维数组的索引转换为二维矩阵的行列mid_value = matrix[mid // n][mid % n]# 注意！！！# mid 是 一维索引# mid_value 是根据一维索引找到的二维数组对应的值！# 用mid_value 跟 target对比# 根据结果改边界应该是mid！！！if mid_value < target:left = mid + 1elif mid_value > target:right = mid - 1else:return Truereturn False

这两种写法的思路是一样的，都是将二维矩阵看作一个一维数组进行二分查找。

区别如下：

1. 变量命名略有不同：
   • 第一种写法中使用row和col分别表示中间元素在二维矩阵中的行和列索引；第二种写法中使用mid_value表示根据一维索引mid找到的二维数组对应的值，通过mid // n和mid % n来隐式地表示行和列索引，没有单独的变量名来显式表示行和列。
2. 注释风格不同：
   • 第二种写法中有更详细的注释，对关键步骤进行了解释说明，有助于理解代码逻辑。
3. 中间变量计算方式稍有不同：
   • 在计算中间索引时，第一种写法使用mid = left + (right - left) // 2，第二种写法使用mid = (left + right) // 2。两种方式在大多数情况下效果相同，但在一些边界情况下可能会有不同的表现。第一种方式可以更好地避免整数溢出问题。

总体来说，两种写法的核心思路和功能是相同的，只是在一些实现细节上有所不同。

还有一种暴力解法

class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:# 暴力破解法，不利用升序性质# 遍历矩阵每一行for row in matrix:# 在当前行中遍历每个元素for elem in row:# 如果找到目标元素就返回trueif elem == target:return Truereturn False