题目的主要信息：

• 矩阵的行元素和列元素都是有序的，从左到右递增，从上到下递增，完全递增元素不会有重复
• 找到矩阵中有没有给定元素即可

方法一：暴力法

具体做法：

从上到下每行，每行中从左至右遍历二维数组，依次查找。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.size() == 0)  //优先判断特殊
            return false;
        int n = array.size();
        if(array[0].size() == 0)  
            return false;
        int m = array[0].size();
        for(int i = 0; i < n; i++)  //两层循环，遍历二维数组
            for(int j = 0; j < m; j++)
                if(array[i][j] == target)  //找到target
                    return true;
        return false;
    }
};

复杂度分析：

• 时间复杂度：$O(nm)O(nm)$，二维数组的遍历
• 空间复杂度：$O(1)O(1)$，没有使用额外空间

方法二：二分查找

具体做法：

既然矩阵里面的元素是有序且无重复的，我们可以好好利用一下。

首先看四个角，左上与右下必定为最小值与最大值，而左下与右上就有规律了： 左下元素大于它上方的元素，小于它右方的元素，右上元素与之相反。 我们可以在查找时使用二分法： 首先以左下角为起点，若是它小于目标元素，则往右移动去找大的，若是他大于目标元素，则往上移动去找小的。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.size() == 0)  //优先判断特殊
            return false;
        int n = array.size();
        if(array[0].size() == 0)  
            return false;
        int m = array[0].size();
        for(int i = n - 1, j = 0; i >= 0 && j < m; ){ //从最左下角的元素开始往左或往上
            if(array[i][j] > target)   //元素较大，往上走
                i--;
            else if(array[i][j] < target) //元素较小，往右走
                j++;
            else
                return true;
        }
        return false;
    }
};

复杂度分析：

• 时间复杂度：$O(m+n)O(m+n)$，最多经过一行一列
• 空间复杂度：$O(1)O(1)$，没有使用额外空间