题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
例子输入： 1 2 8 9 2 4 9 12 4 7 10 13 6 8 11 15
输入整数：7
输出：true
分析：首先我们选取数组右上角的数字9，并且9是第4列最小的数字，9>7，7不会出现在第四列。于是第4列从需要考虑的区域内剔除。 1 2 8 2 4 9 4 7 10 6 8 11 在剩下的矩阵中，右上角的数字是8，同样8大于7，因此剔除第3列。 1 2 2 4 4 7 6 8
在剩余的两列数组中，数字2位于数组的右上角。2小于7，那么要查找的7可能在2的右边，也有可能在2的下边。在前面的步骤中，我们已经剔除2右边的列，因此7只有可能出现在2的下边。于是我们把数字2所在的行也剔除，只分析剩下的三行两列数字。 2 4 4 7 6 8
在剩下的数字中，数字4位于右上角，4小于7，把数字4所在的行也剔除。最后只剩下两行两列的数字。在剩下的数字中，位于右上角的刚好就是我们要查找的数字7，查找过程结束。返回true 4 7 6 8 总之就是：从有效区域数组的最右上角的那个数字(假设为X)着手考虑，若X>要查找的数字，就剔除当前X所在的列；若X<要查找的数字，就剔除X所在的行。每一次都从有效数组的最右上角考虑。
bool Find(int target, vector<vector<int> > array) { int rows = array.size(); //二维数组的行数 int cols = array[0].size(); //二维数组的列数 bool found = false; //标记初始化为false int row = 0, col = cols -1; //从数组的最右上角的数字开始查找 while (row < rows && col >= 0) { if(array[row][col] == target) { found = true; break; } else if(array[row][col] > target) //若当前右上角的数字大于target,剔除这一列 --col; else //若当前右上角的数字大于target,剔除这一行 ++row; } return found; }