搜索二维矩阵 II

240. 搜索二维矩阵 II - 力扣（LeetCode）

问题简述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。
该矩阵具有以下特性：
    每行的元素从左到右升序排列。
    每列的元素从上到下升序排列。

思路

• 二分查找的核心是将搜索区域分成两个部分，且这两个部分具有相反的性质，每次可以排除一半左右搜索区域；

• 对本题来说，从右上角开始遍历，则所有左边的值都比当前值小，所有下方的值都比当前值大；每次可以排除一半区域;

• 时间复杂度：O(M+N)

Python

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        i, j = 0, n - 1
        while i < m and j >= 0:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:  # 比当前值大，横向往左进一格
                j -= 1
            else:  # matrix[i][j] < target 比当前值小，纵向往下进一格
                i += 1
        return False