AcWing 刷题笔记：15. 二维数组中的查找

这题看起来像“有序数组 + 查找”，很容易第一眼就想上二分。
但它的排序关系是“每行递增、每列递增”，并不保证上一行末尾小于下一行开头，所以不能把整个矩阵拉平后直接做二分。

题目特点

给定一个二维数组：

每一行从左到右递增。
每一列从上到下递增。

判断目标值 target 是否在数组中出现。

正确思路

从右上角开始查找（也可以从左下角，原理一样）。

设当前点为 (i, j)：

如果 array[i][j] == target，直接返回 true。
如果 array[i][j] > target，说明当前列下面元素更大，这一列不可能有答案，j-- 向左走。
如果 array[i][j] < target，说明当前行左侧元素更小，这一行不可能有答案，i++ 向下走。

每一步都能排除一整行或一整列，直到越界结束。

复杂度分析

时间复杂度：O(m + n)
空间复杂度：O(1)

其中 m 为行数，n 为列数。

C++ 代码实现

class Solution {
public:
    bool searchArray(const vector<vector<int>>& array, int target) {
        if (array.empty() || array[0].empty()) return false;

        int i = 0;
        int j = (int)array[0].size() - 1;

        while (i < (int)array.size() && j >= 0) {
            if (array[i][j] == target) return true;
            if (array[i][j] > target) {
                --j;
            } else {
                ++i;
            }
        }

        return false;
    }
};

易错点记录

循环条件要写成 j >= 0，否则会漏掉第 0 列。
参数建议用 const vector<vector<int>>&，避免拷贝整个二维数组。
注意处理空数组和空行：array.empty() 或 array[0].empty()。

总结

这题是一个很经典的“利用单调性逐步缩小搜索空间”模型。
右上角策略的妙处在于：每次比较后，移动方向是唯一确定的，不会回头，也不会漏解。
以后遇到“行列分别有序”的二维查找题，优先考虑这种线性扫描思路，通常比硬套二分更稳。

TK的小站

AcWing刷题笔记-15-二维数组中的查找