面试题：二维数组中的查找

题目描述：

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

例如在如下的数组中查找数字7的过程如下：

数组： 1    2     8      9

           2    4     9     12

           4    7    10    13

           6    8    11    15

该查找过程为：

首先选取数组右上角的数字。如果该数字等于要查找的数字，则查找过程结束；如果该数字大于要查找的数字，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。

如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围之内剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。

参考代码为：

//在二维数组中查找：使用vector传参
class Solution {
public:
	bool Find(int target, vector<vector<int>> array) {
		int rows = array.size();
		int columns = array[0].size();
		bool found = false;
		while(!array.empty() && rows > 0 && columns > 0)
		{
			int row = 0;
			int column = columns - 1;
			while(row < rows && column >= 0)
			{
				if(array[row][column] == target)
				{
					found = true;
					return found;
				}
				else if(array[row][column] > target)
					--column;
				else
					++row;
			}
		}
		return found;
	}
};

int main()
{
	Solution sol;
	int ret;
	int target;
	vector<vector<int>> vec;
	vector<int> a;
	vector<int> b;
	vector<int> c;
	vector<int> d;
	a.push_back(1);
	a.push_back(2);
	a.push_back(8);
	a.push_back(9);
	b.push_back(2);
	b.push_back(4);
	b.push_back(9);
	b.push_back(12);
	c.push_back(4);
	c.push_back(7);
	c.push_back(10);
	c.push_back(13);
	d.push_back(6);
	d.push_back(8);
	d.push_back(11);
	d.push_back(15);

	vec.push_back(a);
	vec.push_back(b);
	vec.push_back(c);
	vec.push_back(d);
	
	cout << "请输入要查找的数字：";
	cin >> target;
	ret = sol.Find(target,vec);
	cout << "是否找到该元素：";
	cout << ret << endl;     
	return 0;
}

---------------------------------------------------------------------------------------------------------
//使用数组名传参
    bool FindInArray(int* matrix, int rows, int columns, int target)
    {
        bool found = false;
        if(matrix != NULL && rows > 0 && columns > 0)
        {
            int row = 0;
            int column = columns - 1;
            while(row < rows && column >= 0)
            {
                if(matrix[row * columns + column] == target)
                {
                    found = true;
                    return found;
                }
                else if(matrix[row * columns + column] > target)
                    --column;
                else
                    ++row;
            }
        }
        return found;
    }

int main()
{
    int a[][4] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
    int ret,target;
    int row = sizeof(a)/sizeof(a[0]);
    int column = sizeof(a[0])/sizeof(a[0][0]);
    cout << "请输入要查找的数字：";
    cin >> target;
    ret = FindInArray((int*)a,row,column,target);
    cout << "是否找到该元素：";
    cout << ret << endl;
    return 0;
}

运行结果：