力扣热题100_二分查找_74_搜索二维矩阵
文章目录
- 题目链接
- 解题思路
- 解题代码
题目链接
74. 搜索二维矩阵
给你一个满足下述两条属性的 m x n 整数矩阵：
- 每行中的整数从左到右按非严格递增顺序排列。
- 每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。
示例 1：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true
示例 2：
输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false
解题思路
全局二分
这个方法，是我们在二维矩阵上进行二分查找，这其实相当于把二维矩阵当做一维来做，要求每一行的最后一个元素小于下一行的第一个元素。
根据 mid 求出在二维矩阵中的具体位置，然后判断 left 和 right 的移动方式。整体做法和一维数组的二分没有区别。
解题代码
class Solution:def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:M, N = len(matrix), len(matrix[0])left, right = 0, M * N - 1while left <= right:mid = left + (right - left) // 2cur = matrix[mid // N][mid % N]if cur == target:return Trueelif cur < target:left = mid + 1else:right = mid - 1return False
参考资料：力扣热题100对应的题解