AcWing 15 二维数组中的查找

题目描述：

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

样例

输入数组：

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

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

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

分析：

本题考察在O（max（n，m））时间复杂度内实现元素的查找，当然，直接遍历二维数组的方法就不用介绍了。

首先，鉴于平时用vector<vector<int>> array表示二维数组较少，先分析下它与普通二维数组的不同之处。

假设有vector<vector<int>> v1，与int v2[m][n]两个二维数组。

v1[0].size（）表示第一行元素的个数（本题是二维数组所以各行元素个数都是它），v1.size（）表示二维数组的行数，v2.size（）表示二维数组元素的个数，这点要区别，我们将vector<int>视为自定义的数据类型，v1.size（）就是指向量中含有多少个这种类型元素。

下面分析本题的思路：

本题在邓公的习题集上也出现了，我们主要利用各行各列都递增的性质。先考察右上角元素，如果待查找元素x大于它，则往下查找，否则向左查找，直到访问到边界为止。

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