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.

Example:

The existing matrix matrix is as follows:

[[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]Copy the code
Given target = 5, return true. Given target = 20, return false.Copy the code

Limitations:

0 <= n <= 1000
0 <= m <= 1000
Copy the code

Answer 1:

Violent solution

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        for l in matrix:
            if target in l:
                return True
        return False
Copy the code

If you do this in an interview, the interviewer will probably just say, “That’s it for today.”

Answer 2:

A binary tree search algorithm is used to determine the index number from upper right to lower left (or lower left to upper right) in an ordered two-dimensional array, subtracting columns by 1 if the index is greater than target and rows by 1 if it is less than target.

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if len(matrix) == 0 or len(matrix[0]) == 0:
            return False
        m = len(matrix)
        n = len(matrix[0])
        row = 0
        col = n - 1
        while row <= m-1 and col >=0:
            if matrix[row][col] == target:
                return True
            elif matrix[row][col] > target:
                col -= 1
            else:
                row += 1
        return False
Copy the code