剑指offer_二维数组中的查找

题目描述

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

思路：

• 因为是从左往右递增的，可以从每一行的最末尾开始找。

• 如果整数大于数组数字，说明得减小数字，数组中右边的比他大，下面的比它大，所以走左边。

• 如果整数小于数组数字，说明得增大数组，然后由于我们是从每行末尾从右往左扫描的，所以增大的话就往下边走

row=(int)array.size();

col=(int)array[0].size();

注意：若数字小于第一行第一列，或者大于最后一行最后一列，说明不存在该数组中

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