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

算法思路：

因为数组的每一行和每一列都是递增的，所以我们可以从数组的右上角开始查找，如果目标数比当前位置的数大，就往下移动一行；如果目标数比当前位置的数小，就往左移动一列；如果相等，直接返回 true；如果超出了数组的边界，则说明数组中不含有该整数，返回 false。

时间复杂度：$O(m+n)$，其中 $m$ 是数组的行数，$n$ 是数组的列数。

代码实现：

C++ 代码：

bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
    if (matrix.empty()) return false;
    int m = matrix.size(), n = matrix[0].size();
    int i = 0, j = n - 1;
    while (i < m && j >= 0) {
        if (matrix[i][j] == target) {
            return true;
        } else if (matrix[i][j] < target) {
            i++;
        } else {
            j--;
        }
    }
    return false;
}

Java 代码：

public boolean findNumberIn2DArray(int[][] matrix, int target) {
    if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
        return false;
    }
    int m = matrix.length, n = matrix[0].length;
    int i = 0, j = n - 1;
    while (i < m && j >= 0) {
        if (matrix[i][j] == target) {
            return true;
        } else if (matrix[i][j] < target) {
            i++;
        } else {
            j--;
        }
    }
    return false;
}

Python 代码：

def findNumberIn2DArray(matrix: List[List[int]], target: int) -> bool:
    if not matrix:
        return False
    m, n = len(matrix), len(matrix[0])
    i, j = 0, n - 1
    while i < m and j >= 0:
        if matrix[i][j] == target:
            return True
        elif matrix[i][j] < target:
            i += 1
        else:
            j -= 1
    return False