JZ1 二位数组中的查找

题目描述

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

思路

关键点：左下角的元素
对于数组中的每一个元素，比它小的可能在它上面，可能在它左边，但是对于左下角元素来说，比它大的在它右边(此时这一列可以剔除)，比它小的在它上面(此时这一行可以剔除)；抓住这一点，从左下角这个元素开始与目标值进行比较，小了就往上，大了就往右；结束条件：找到这个元素，返回true；直到碰壁还没找到，返回false

伪代码

二维数组的行列：m，n
i=m-1,j=0—定义左下角元素
循环：结束条件(相等，或者碰壁)；循环体内部进行比较

代码

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int m = array.size();    //行数
        int n = array[0].size();  //列数
        if(m==n&&m==0)  //若数组为空则直接返回false
            return false;
        int i=m-1;   //定义左下角元素
        int j=0;
        while(i>=0&&j<n)  //碰壁的时候结束
        {
            if(target == array[i][j])  //找到了
                return true; 
            if(target>array[i][j])   //大了就往右
                j++;
            else   //小了就往上
                i--;
        }
        return false;
    }
};