LCR 121.寻找目标值
难度：🟡 中等
标签：数组、二分查找、矩阵
链接：LCR 121. 寻找目标值 - 二维数组 (剑指 Offer 04. 二维数组中的查找)
题目描述
在一个 m*n 的二维数组 plants 中，每一行都按照从左到右的顺序递增，每一列都按照从上到下的顺序递增。请设计一个高效的算法，判断 target 是否在该二维数组中。
示例 1：
现有 `plants` 矩阵如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
解题思路
核心思想
本题的核心是利用矩阵的特殊“双重有序”特性。即每一行从左到右递增，每一列从上到下递增。这个特性使得我们可以从一个特定的角出发，通过比较大小，在每一步都能排除掉一整行或一整列，从而高效地缩小搜索范围。
思路选择
Z字形查找（或称为“右上角/左下角查找法”） 是解决此问题的最优思路。
如果我们从右上角开始：当前值比
target大，则target不可能在当前列，可以向左移动；当前值比target小，则target不可能在当前行，可以向下移动。如果我们从左下角开始（如代码所示）：当前值
plants[row][col]是其所在行的最小值，是其所在列的最大值。如果
plants[row][col] < target，说明target一定不在当前行（因为当前行其他元素都比它大），所以我们可以向上移动一行 (row--)。如果
plants[row][col] > target，说明target一定不在当前列（因为当前列其他元素都比它小），所以我们可以向右移动一列 (col++)。
这种方法每一步都能排除一行或一列，效率很高。
关键步骤
处理边界情况：如果矩阵为空，直接返回
false。初始化指针：将指针定位到矩阵的左下角，即
row = plants.length - 1,col = 0。循环搜索：当指针还在矩阵范围内时（
row >= 0且col < plants[0].length），持续循环。 a. 获取当前指针指向的值plants[row][col]。 b. 如果该值等于target，说明找到了，返回true。 c. 如果该值小于target，说明target可能在右侧，向右移动列指针col++。 d. 如果该值大于target，说明target可能在上方，向上移动行指针row--。返回结果：如果循环结束仍未找到目标值，说明矩阵中不存在
target，返回false。
代码实现
/**
* @param {number[][]} plants
* @param {number} target
* @return {boolean}
*/
var findTargetIn2DPlants = function (plants, target) {
// 边界情况：矩阵为空
if (plants.length === 0) return false;
// 从左下角开始
let row = plants.length - 1, col = 0;
// 当指针在矩阵范围内时
while (row >= 0 && col < plants[0].length) {
if (plants[row][col] === target) {
return true;
}
// 如果当前值小于目标，向右搜索
if (plants[row][col] < target) {
col++;
}
// 如果当前值大于目标，向上搜索
else {
row--;
}
}
// 搜索完毕未找到
return false;
};
复杂度分析
时间复杂度：O(m + n) 其中 m 是矩阵的行数，n 是矩阵的列数。指针
row最多移动 m 次，指针col最多移动 n 次，总的移动次数不超过m + n。空间复杂度：O(1) 我们只使用了
row和col两个额外变量，空间消耗是恒定的。
相关题目
总结
本题的解法非常巧妙，它利用了矩阵的双重有序性，将二维的搜索问题降维成线性的搜索路径。这种从特定角落开始，每步排除一行或一列的“降维打击”思想，是处理这类矩阵搜索问题的经典模式。