1. Problem description:

Write an efficient algorithm to search for a target value target in an m x n matrix. This matrix has the following properties: The elements of each row are arranged in ascending order from left to right.
The elements of each column are arranged in ascending order from top to bottom.

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]
]

Returns true given target = 5.
Given target = 20, return false.

2. Thought analysis:

① From the title, we can know that the right and downward directions are in ascending order, so it is natural to think of using binary search to solve the problem. We can find the corresponding column in each row, and then find the corresponding column in the column. To see if the element exists, finding elements in rows and columns can be solved by using binary search. We can declare a method, and pass a parameter in the method to indicate whether to search for rows or columns, and then perform binary search.

② Because we can search to the right first, and then search downward, we are faced with these two choices for each element in the matrix, so in addition to using the binary search method, we can also use the recursive method. We can recursively Judging from the method, when the current recursive element is greater than the target, then return directly to the previous layer and try other element values. We can write a recursive method with a return value, as long as it is recursive to the right and recursive to the right. If one is established, it means that the target has been found.

3. The code is as follows:

Binary search:

import sys
from typing import List


class Solution:
    def binarySearch(self, l: int, r: int, matrix: List[List[int]], flag: int, x: int, target: int):
        # binary search column
        mid = 0
        # Set the flag to indicate whether to search in the row or in the column
        if flag == 0:
            # Find columns in the same row
            while l <= r:
                mid = (l + r) // 2
                if matrix[x][mid] == target:
                    return mid
                elif matrix[x][mid] < target:
                    l = mid + 1
                else:
                    r = mid - 1
            if matrix[x][mid] > target: return mid - 1
            return mid
        else:
            # Find rows in the same column
            mid = 0
            while l <= r:
                mid = (l + r) // 2
                if matrix[mid][x] == target:
                    return mid
                elif matrix[mid][x] < target:
                    l = mid + 1
                else:
                    r = mid - 1
            return mid

    def searchMatrix(self, matrix, target):
        if len(matrix) == 0 or len(matrix[0]) == 0: return False
        for i in range(len(matrix)):
            col = self.binarySearch(0, len(matrix[0]) - 1, matrix, 0, i, target)
            row = self.binarySearch(0, len(matrix) - 1, matrix, 1, col, target)
            if matrix[row][col] == target: return True
        return False

Recursive:

import sys
from typing import List


class Solution:
    # Matrix rows and columns
    row, col, max = 0, 0, sys.maxsize

    """
    :param r: the position of the current recursive line
    :param c: the position of the current recursive column
    """

    def dfs(self, matrix: List[List[int]], target: int, r: int, c: int):
        if r == self.row or c == self.col: return False
        if matrix[r][c] == self.max: return False
        if matrix[r][c] == target: return True
        if matrix[r][c] > target: return False
        # Mark visited locations
        matrix[r][c] = self.max
        right = self.dfs(matrix, target, r, c + 1)
        down = self.dfs(matrix, target, r + 1, c)
        return right or down

    def searchMatrix(self, matrix, target):
        if len(matrix) == 0 or len(matrix[0]) == 0: return False
        self.row, self.col = len(matrix), len(matrix[0])
        return self.dfs(matrix, target, 0, 0)