文章目录

在二维数组中查找

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

利用该二维数组的性质：

  • 每一行都按照从左到右递增的顺序排序，
  • 每一列都按照从上到下递增的顺序排序

所以，对于左下角的值 m，它是该行最小的数，又是该列最大的数。可以从这里开始比较，按行按列前进。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int m(array.size()), n(array[0].size());
        if(m==0 or n==0) return false;
        int i(m-1), j(0);
        while(i>=0 && j<n){
            if(target == array[i][j]) return true;
            if(target > array[i][j]) j++;
            if(target < array[i][j]) i--;
        }
        return false;
    }
};