在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，
每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，
输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

matrix=[
  [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]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。

>本题目中说明从左到右是递增顺序，从上到下同样为递增
>所以该矩阵可以看成是一个二叉搜索树
>比如我们把15看成根节点，如果比15小那么向左寻找
>如果比15大，那么就向下寻找
>
>所以可以用深度优先遍历，不断的递归寻找，但是本题目不需要visit数组，
>因为只有两条道路，所以不会进行回调

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if len(matrix)==0:
            return False
        return self.dfs(matrix, 0, len(matrix[0]) - 1, target)
    def dfs(self,matrix, i, j, target):
        if i < 0 or j < 0 or i >= len(matrix) or j >= len(matrix[0]):
            return False
        res = ""
        if matrix[i][j] < target:
            res = self.dfs(matrix, i + 1, j, target)
        elif matrix[i][j] > target:
            res = self.dfs(matrix, i, j - 1, target)
        else:
            return True
        return res

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if(matrix.length==0){
            return false;
        }
        return dfs(matrix, 0, matrix[0].length - 1, target);
    }
    public boolean dfs(int[][] matrix, int i, int j, int target) {
        if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length) {
            return false;
        }
        boolean res;
        if (matrix[i][j] < target) {
            res = dfs(matrix, i + 1, j, target);
        } else if (matrix[i][j] > target) {
            res = dfs(matrix, i, j - 1, target);
        } else {
            return true;
        }
        return res;
    }
}