题目
在一个二维数组中，每一行从左到右递增，每一列从上到下递增。请判断数组中是否含有整数 num。
示例矩阵：
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
思路
暴力 (O(nm)) 可过小数据，但利用单调性可做到 (O(n+m))：
从 右上角 出发（当前值 t）：
t == num：找到t > num：该列下面更大，删当前列（--col）t < num：该行左边更小，删当前行（++row）
从左下角出发对称。每次排除一行或一列，故线性。
代码（一维数组模拟矩阵）
bool Find(const int* matrix, int rows, int cols, int num) {
if (matrix == nullptr || rows <= 0 || cols <= 0) return false;
int row = 0;
int col = cols - 1;
while (row < rows && col >= 0) {
int t = matrix[row * cols + col];
if (t == num) return true;
if (t > num) --col;
else ++row;
}
return false;
}
旧笔记写 matrix != null 是 Java/C# 习惯；C++ 用 nullptr。
正确性直觉
右上角是所在行最大、所在列最小（在单调假设下）。比较一次就能扔掉一整行或一整列，不会漏解。
复杂度
- 时间 (O(rows+cols))
- 空间 (O(1))
变形
- 行列严格递增条件减弱时，算法可能失效
- 若只要任一出现位置，可返回坐标
- 与二分每行 (O(n\log m)) 相比，数据接近方阵时本解法更优
小结
这是「利用有序二维结构缩小搜索空间」的经典题。记住 右上角出发 + 删行删列，比背代码更重要。
走查示例
在文中矩阵找 7：右上角 9 → 大于 7，删列 → 见 2 → 小于 7，删行 → … 最终在 7 处命中。
找 5：路径会走到边界外，返回 false。
实现提醒
- 空指针、0 行 0 列
row * cols + col防写反- 面试口述「为什么每次能删一行/列」比背代码分更高
把单调二维结构上的搜索当成一类题：右上角/左下角起步是固定套路。