剑指 Offer 04. 二维数组中的查找

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

方法1：暴力（时间复杂度：O(nm)，空间复杂度：O(1)）

直接遍历整个二维数组的每一个元素，判断目标值是否在二维数组中存在。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.empty())
        	return false;
        for(int i=0;i<array.size();i++)
		{
			for(int j=0;j<array[0].size();j++)
			{
				if(array[i][j]==target)
				{
					return true;
				}
			}
		 } 
		return false;
    }
};

方法2：线性查找（时间复杂度：O(n+m)，空间复杂度：O(1)）

由于给定的二维数组具备每行从左到右递增以及每列从上到下递增的特点，当访问到一个元素时，可以排除数组中的部分元素。

从二维数组的右上角开始查找。如果当前元素等于目标值，则返回 true。如果当前元素大于目标值，则移到左边一列。如果当前元素小于目标值，则移到下边一行。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.empty())
        	return false;
        int cur_row=0;
        int cur_col=array[0].size()-1; 
		while((cur_row<array.size())&&(cur_col>-1))
		{
			if(array[cur_row][cur_col]<target)
				cur_row++;
			else if(array[cur_row][cur_col]>target)
				cur_col--;
			else
				return true;
		}
		
		return false;
    }
};