力扣热题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 - 1
        while left <= right:
            mid = left + (right - left) // 2
            cur = matrix[mid // N][mid % N]
            if cur == target:
                return True
            elif cur < target:
                left = mid + 1
            else:
                right = mid - 1
        return False

参考资料：力扣热题100对应的题解