力扣对应题目链接：240. 搜索二维矩阵 II - 力扣（LeetCode）
牛客对应题目链接：二维数组中的查找__牛客网 (nowcoder.com)
核心考点：数组相关，特性观察，时间复杂度把握。
一、《剑指Offer》对应内容
二、分析题目
- 正常查找的过程本质就是排除的过程，谁排除的效率更高，谁对应查找的效率也就更高。
- 如果双循环查找，本质是一次排除一个，效率过低。但采取从右上角 / 左下角进行比较，这样就可以一次排除一行或一列。
- 注意临界条件。
三、代码（C++）
1、从右上角开始排查
//从右上角开始排查 class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int i=0, j=matrix[0].size()-1; while(i<matrix.size() && j>=0) { if(matrix[i][j]>target) j--; else if(matrix[i][j]<target) i++; else return true; } return false; } };
注意：本题因为所提供数据范围为：
m == matrix.lengthn == matrix[i].length1 <= n, m <= 300所以，排除了空数组的情况，否则还需要在开头进行特判。
例如，下面这道题目：LCR 121. 寻找目标值 - 二维数组 - 力扣（LeetCode）
//从右上角开始排查 class Solution { public: bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) { if(plants.size()==0 || plants[0].size()==0) return false; int i=0, j=plants[0].size()-1; while(i<plants.size() && j>=0) { if(plants[i][j]>target) j--; else if(plants[i][j]<target) i++; else return true; } return false; } };
注意：如果采用第二种方法：“从左下角开始排查”，则不需要进行特判，因为如果数组为空，第二种方法并不会进入到循环当中。
//从左下角开始排查 class Solution { public: bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) { int i=plants.size()-1, j=0; while(i>=0 && j<plants[0].size()) { if(plants[i][j]>target) i--; else if(plants[i][j]<target) j++; else return true; } return false; } };
2、从左下角开始排查
//从左下角开始排查 class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int i=matrix.size()-1, j=0; while(i>=0 && j<matrix[0].size()) { if(matrix[i][j]>target) i--; else if(matrix[i][j]<target) j++; else return true; } return false; } };
