The title

In an N by m two-dimensional array, each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Perform an efficient function that takes such a two-dimensional array and an integer and determines whether the integer is in the array.

Answer key

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) - >bool:
        if not matrix:
            return False

        n = len(matrix)
        m = len(matrix[0])

        if m == 0 or n == 0:
            return False
        i = n-1
        while i>=0:
            for j in range(m):
                if matrix[i][j] == target:
                    return True
                if matrix[i][j]>target:
                    i-=1
                    break
                if j==m-1:
                    return False
        return False
Copy the code

Train of thought

Similar to sorting binary trees, the bottom right of an array element is greater than it, and the top left is less than it, so start at the bottom left of the array, move up one level if target is less than it, move right if target is greater than it, return True if target is found, and return False if not found.