二维数组中的查找----newcoder

题目描述

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

newcoder 题目链接

• 题解：
  拿到这个题，第一种思路就是遍历一遍
  这是一个时间复杂度为 O(n²) 的办法

代码如下：

#include <iostream>
#include <vector>

class Solution {
public:
    bool Find(int target, std::vector<std::vector<int> > array) {
        for(size_t i = 0; i < array.size(); ++i)
        {
            for(size_t j = 0; j < array[i].size(); ++j)
            {
                if(array[i][j] == target)
                {
                    return true;
                }
            }
        }

        return false;
    }

};

可以通过oj，但是仔细阅读题目发现没有充分利用题目的条件，我们再来阅读一遍题目：

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

我们就可以利用这个条件，

• 我们把二维数组想象成一个矩阵
• 如果当前矩阵的最右上角元素小于目标值，那第一行就排除搜索范围了