搜索二维矩阵【二分】-Toy模板网

这篇具有很好参考价值的文章主要介绍了搜索二维矩阵【二分】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Problem: 74. 搜索二维矩阵

思路 & 解题方法

可以二分一次，也可以二分两次。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O (l o g n + l o g m)$

空间复杂度:

添加空间复杂度, 示例： $O (1)$ 文章来源地址https://www.toymoban.com/news/detail-786784.html

二分两次

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        top, but = 0, m - 1
        while top < but:
            mid = (top + but) // 2
            if matrix[mid][-1] < target:
                top = mid + 1
            elif matrix[mid][-1] >= target:
                but = mid
        if but >= 0 and but < m:
            left, right = 0, n - 1
            l = matrix[but]
            while left <= right:
                mid = (left + right) // 2
                if l[mid] > target:
                    right = mid - 1
                elif l[mid] < target:
                    left = mid + 1
                else:
                    return True
        return False

二分一次

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        for l in matrix:
            if l[-1] < target:
                continue
            else:
                left, right = 0, n - 1
                while left <= right:
                    mid = (left + right) // 2
                    if l[mid] < target:
                        left = mid + 1
                    elif l[mid] > target:
                        right = mid - 1
                    else:
                        return True
                break
        return False