剑指offer：1.二维数组中的查找

题目

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

样例

输入数组：

[
  [1,2,8,9]，
  [2,4,9,12]，
  [4,7,10,13]，
  [6,8,11,15]
]

如果输入查找数值为7，则返回true，

如果输入查找数值为5，则返回false。

解题思路

开始因为牛客网上的题目坑爹的没有样例理解错题目以为是整个有序的就直接用二分法了结果错误了，后面去leetcode上搜了一下看到样例才明白题目的意思。问题的关键是抓住右上角那个关键的点，右上角的点比同行的左边的大比同列的下面的小，所以每次拿右上角的点和目标数字进行比较。如果相等则找到小于目标则可以排除一行，如果大于目标则可以排除一列如此迭代最后就可以得到结果了，实际的代码如下所示：

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