【剑指offer】-二维数组中的查找-蒲公英云

【剑指offer】-二维数组中的查找

题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。例如：下面的数组

1 2 8 9

2 4 9 12

4 7 10 13

6 8 11 15

则在数组中查找7，就存在。

解析：我们可以从数组的一个角上选取一个数来和要查找的数进行比较。假如我们选的是右上角，则7比9要小。由于每列都是递增的，则7不可能出现在第4列中。于是，我们可以把第四列剔除。选取下一个右上角的数字为8，7比8也要小，因此我们把第三列也剔除掉。下一个右上角的数字为2,7比2要大，因此我们把第一行剔除掉。因此递归执行操作，直到搜索到要查找的数字或者搜索到左下角时停止。

代码如下：

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