两次二分查找解决该问题，第一次可能在哪一行，第二次找这一行中是否真的存在 target 。

题目

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
- 每行中的整数从左到右按升序排列。
- 每行的第一个整数大于前一行的最后一个整数。

示例

示例 1:

# 输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
# 输出: true

示例 2:

# 输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
# 输出: false

考察知识点

二分查找

核心思想

方法一、一次性二分查找
利用矩阵本身的有序性，先逐行遍历，拼接成一个 list ，然后对这个 list 进行二分查找操作。

方法二、查找第一个大于目标值的数
将问题转化为，查找第一个大于目标值的数，进行两次二分查找。
第一次二分查找，确定 target 所在的行。
第二次二分查找，确定这一行中是否有 target。

方法三、逐行遍历寻找
不进行二分查找，一行一行的遍历过去。

Python版本

• 方法一的实现

from typing import List

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        all_ints = []
        for i in matrix:
            all_ints += i
        left = 0
        right = len(all_ints)
        while left < right:
            mid = left + (right - left) // 2
            if all_ints[mid] == target:
                return True
            elif all_ints[mid] < target:  # 在右区间 左边界右移
                left = mid + 1
            else:  # 在左区间 右边界左移
                right = mid

        return False


Input = [
    [
        [1,   3,  5,  7],
        [10, 11, 16, 20],
        [23, 30, 34, 50]
    ],
    [
        [1,   3,  5,  7],
        [10, 11, 16, 20],
        [23, 30, 34, 50]
    ]
]
Input1 = [3, 13]
Answer = [True, False]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        result = solution.searchMatrix(Input[i], Input1[i])
        if result == Answer[i]:
            print(True)
        else:
            print(False)
            print(Answer[i])
            print(Input[i])

时间复杂度 : 由于是标准的二分查找，时间复杂度为 \(O(log(m \times n))\)。
空间复杂度 : \(O(m\*n)\)。
执行用时 :36 ms, 在所有 Python3 提交中击败了94.68%的用户
内存消耗 :14.4 MB, 在所有 Python3 提交中击败了100.00%的用户

• 方法二的实现

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target):
        if not len(matrix) or not len(matrix[0]): return False
        left, right = 0, len(matrix)
        # 先通过二分查找找到那一行
        while left < right:
            mid = (left + right) // 2
            if matrix[mid][0] == target:  return True
            if matrix[mid][0] <= target:
                left = mid + 1
            else:
                right = mid
        # 为什么要回退，因为找的是第一个大于目标值的数，且位于这一行的首位，所以目标值一定在下一行，如果没有满足条件的，就说明在第一行，select_col=0。
        select_col = right-1 if right > 0 else right  # 如果选中的行是0，就不能回退了，以免越界。
        left, right = 0, len(matrix[select_col])

        # 不一定在这一行，所以还要进一步确定是否在这一行
        while left < right:
            mid = (left + right) // 2
            if matrix[select_col][mid] == target: return True
            if matrix[select_col][mid] < target:
                left = mid + 1
            else:
                right = mid

        return False

时间复杂度 : 两次二分查找，时间复杂度为 \(O(log(m) + log(n))\) 也就是 \(O(log(m \times n))\)，但是这是极少数极端情况，大多数情况下都不会循环这么多次，所以这个方法最好。
空间复杂度 : \(O(1)\)。 执行用时 :28 ms, 在所有 Python3 提交中击败了99.53%的用户
内存消耗 :14.5 MB, 在所有 Python3 提交中击败了100.00%的用户

• 方法三的实现

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not len(matrix) or not len(matrix[0]): return False
        rows, cols = len(matrix), len(matrix[0])
        if rows > 0 and cols > 0:
            row = 0
            col = cols - 1
            while row < rows and col >= 0:
                if matrix[row][col] == target:
                    return True
                elif matrix[row][col] > target:
                    col -= 1
                else:
                    row += 1
        return False

时间复杂度 : \(O(m + n)\)。
空间复杂度 : \(O(1)\)。 执行用时 :60 ms, 在所有 Python3 提交中击败了71.15%的用户 内存消耗 :14.3 MB, 在所有 Python3 提交中击败了100.00%的用户

参考链接

Grandyang
LeetCode用户评论