题解 | #二维数组中的查找#

方法：线性搜索

通过观察二维数组可以发现，左下角的元素是所在列最大的值，是所在行最小的值；右上角的元素是所在列最小的值，是所在行最大的值。如果从左下角或者右上角进行搜索，则一次搜索可以排除一行或者一列的元素。下列以右上角进行搜索：

时间复杂度：0(n+m)

空间复杂度：o(1)

class Solution {
  public:
    bool Find(int target, vector<vector<int> >& array) {
        int col = array.size();
        int row = array[0].size();
        //特殊情况处理
        if (col == 0 || row == 0)
            return false;

        int n = 0;
        int m = row - 1;
        while (n < col && m >= 0) {
		  	//从右上角开始搜索
            if (array[n][m] == target)
                return true;
		  	//小于右上角元素的，排除所在列的元素
            else if (target < array[n][m])
                m--;
		  	//大于右上角元素的，排除所在行的元素
            else
                n++;
        }
        return false;
    }
};