搜索二维矩阵

难度: Medium

给你一个满足下述两条属性的 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

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 100
-10⁴ <= matrix[i][j], target <= 10⁴

Submission

运行时间: 40 ms

内存: 15.2 MB

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        l = 0
        r = len(matrix) - 1
        while l < r:
            mid = l + (r - l) // 2
            print(mid, l, r)
            if matrix[mid][-1] >= target:
                r = mid
            else:
                l = mid + 1

        row = l
        l = 0
        r = len(matrix[row])-1

        while l <= r:
            mid = l + (r - l) // 2
            if matrix[row][mid] == target:
                return True
            elif matrix[row][mid] > target:
                r = mid - 1
            elif matrix[row][mid] < target:
                l = mid + 1
        return False

Explain

该题解采用两次二分查找的思路。首先对矩阵的第一列元素进行二分查找，目的是找到目标值可能所在的行。找到后，再对该行进行二分查找，判断目标值是否存在。

时间复杂度: O(log(m*n))

空间复杂度: O(1)

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        l = 0
        r = len(matrix) - 1
        
        # 第一次二分查找，确定目标值所在的行
        while l < r:
            mid = l + (r - l) // 2
            if matrix[mid][-1] >= target:
                r = mid
            else:
                l = mid + 1
        
        row = l
        l = 0
        r = len(matrix[row])-1
        
        # 第二次二分查找，判断目标值是否在该行中
        while l <= r:
            mid = l + (r - l) // 2
            if matrix[row][mid] == target:
                return True
            elif matrix[row][mid] > target:
                r = mid - 1
            elif matrix[row][mid] < target:
                l = mid + 1
        
        return False

Explore

在这种方法中，选择比较`matrix[mid][-1]`（即每行的最后一个元素）与`target`是因为我们想确认目标值可能所在的行。每行的最后一个元素是该行中最大的，如果`target`小于或等于这个元素，则目标值有可能在这行或更前面的行中。如果我们比较的是每行的第一个元素`matrix[mid][0]`，则只能告诉我们`target`是否可能在这行或更后面的行中，这不足以帮助我们准确锁定目标值的行。

当`matrix[mid][-1]`大于等于`target`时，意味着`target`可能位于当前行或之前的行。将右指针`r`设置为`mid`，而不是`mid + 1`，是为了确保不排除当前行，因为当前行的最后一个元素大于等于`target`，所以`target`有可能正好在这一行。如果我们将`r`设置为`mid + 1`，则当前行会被排除在外，可能会错过包含`target`的行。

第一次二分查找的目的是缩小目标值可能存在的行范围。结束时，`l`和`r`指针将会指向同一行，也就是变量`row`。此时，这一行是唯一一行，其最后一个元素大于等于`target`且前一行的最后一个元素（如果存在）小于`target`。因此，这一行是`target`可能存在的唯一行，接下来只需要在此行进行二分查找即可确定`target`是否真的存在于该行。

如果矩阵中的每一行只包含一个元素，这种二分查找方法仍然有效。在这种情况下，每一行的第一个元素也是最后一个元素，因此第一次二分查找将会找到一个最可能包含`target`的行。然后在这一行（即一个元素）进行第二次二分查找，实际上就是直接比较这一个元素与`target`。因此，整体逻辑不变，依然可以准确地判断`target`是否存在于矩阵中。