一、题目描述
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
二、输入描述
array： 待查找的二维数组
target：查找的数字
三、输出描述
查找到返回true，查找不到返回false
四、牛客网提供的类框架
class Solution {
public:
bool Find(vector<vector<int> > array,int target) {
}
};五、解题思路
这道题类似于一维数组的二分查找。由题目可知矩阵是有序的，从左下角看，向上是递减，向右是递增（也可以从右上角看，向左是递减，向下是递增）。
所以从左下角开始或者从右上角开始查找。对于从左下角开始，当查找位置的数比要查找的数大，如果矩阵中该数存在，那么它将在该位置的上方，所以y坐标–；相反如果现在的位置上的书比要查找的数小，那么它将在该位置的右方，所以x坐标++。当所查找的位置超过矩阵的坐标范围，查找失败（数组中不存在该数）。同样也可以通过右上角开始查找。
六、代码
class Solution {
public:
bool Find(vector<vector<int> > array,int target) {
int row, column, i, j;
row = array.size();
column = array[0].size();
i = row - 1;
j = 0;
while(i >= 0 && j <= column -1)
{
if(array[i][j] < target)
{
j++;
}
else if(array[i][j] > target)
{
i--;
}
else{
return true;
}
}
return false;
}
};