题目描述：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：由于是有序的，我们找个起点开始搜索，注意这个起点一定要能确定一个方向是递减一个是递增的，不然两个决策一样地话就不能搜索了，于是找了右上角作为起点dfs,复杂度 O ( m a x ( r o w , c o l ) ) O(max(row,col)) O(max(row,col))

Code:

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        return dfs(target, array, 0, array[0].size()-1); //O(n)
    }
    
    bool dfs(int target, vector<vector<int> > &arr, int x, int y) {
        if (x == arr.size() || y < 0) return false;
        if (arr[x][y] == target) return true;
        if (arr[x][y] > target) return dfs(target, arr, x, y-1);
        return dfs(target, arr, x+1, y);
    }
};