【力扣】240：搜索二维矩阵 II

题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

来源：力扣（LeetCode）

算法思路

二分

class Solution:
    def findNumberIn2DArray(self, matrix, target: int) -> bool:
        def BS(ls):
            l,r=0,len(ls)-1
            while l<=r:
                mid=(l+r)//2
                if ls[mid]==target:return True
                if ls[mid]>target:r=mid-1
                else:l=mid+1
            return False
        for i in matrix:
            if BS(i):return True
        return False

IMPROVE

大佬的操作：从矩阵右上角往左下看！

从这个角度看，假设任意一点K，K的左边的值都小于K，K的下面的值都大于K。

class Solution:
    def searchMatrix(self, matrix, target):
        if not matrix or not matrix[0]:return False
        m,n=len(matrix),len(matrix[0])

        i,j=0,n-1
        while 0<=i<m and 0<=j<n:
            if matrix[i][j]==target:return True
            if matrix[i][j]>target:
                j-=1
            else:
                i+=1
        return False