在二维数组中查找

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

利用该二维数组的性质:

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

所以,对于左下角的值 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;
    }
};