题解 | #二维数组中的查找#

暴力解法

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.size()==0)return false;
        for(int i=0;i<array.size();i++){
            int end=array[i].size()-1;
            if(array[i].size()==0) continue;
            if(target>array[i][end]) continue;
            if(target<array[i][0]) return false;
            //int mid=0;
            for(int j=0;j<array[0].size();j++){
                if(array[i][j]==target) return true;
            }
        }
        return false;
    }
};

注意判空

一维二分查找

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.size()==0)return false;
        for(int i=0;i<array.size();i++){
            int end=array[i].size()-1;
            if(array[i].size()==0) continue;
            if(target>array[i][end]) continue;
            if(target<array[i][0]) return false;
            int l=0,r=end,mid=l+(r-l)/2;
            while(l<=r){
                mid=l+(r-l)/2;
                if(target>array[i][mid]) l=mid+1;
                else if(target<array[i][mid]) r=mid-1;
                if(target==array[i][mid]) return true;
            }
        }
        return false;
    }
};

mid=l+(r-l)/2;是为了防止越界
循环持续条件是l<=r
target大了l=mid+1
小了 r=mid-1

二维二分查找

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

因为二分需要确定状态，朝着一个明确的方向移动，所以需要选择左下角或者右上角作为起点。不管是大还是小都有明确的移动方向。如果选左上角，那target>array时朝着两个方向走都更大，不知道向哪走。