C++实现二维数组的搜索（剑指Offer经典题）
 
在计算机专业的算法学习中，二维数组的搜索是非常基础且高频的考点，尤其是每行每列都按升序排列的二维数组查找问题，更是面试和笔试中的常客。今天就给大家分享一种简单高效的解法，用C++轻松实现这个经典题目。
 
一、题目描述
 
给定一个 m x n 的二维数组，该数组具有以下特性：
 
1. 每行的元素从左到右按升序排列；
2. 每列的元素从上到下按升序排列。
要求编写一个函数，判断目标值是否存在于该二维数组中。
 
二、解题思路
 
直接暴力遍历整个二维数组的时间复杂度是O(mn)，效率较低。我们可以利用数组行和列升序的特性，选择右上角作为起始查找点，通过比较逐步缩小范围：
 
1. 初始时，行索引 i=0 ，列索引 j = 列数-1 （即右上角元素）；
2. 如果当前元素等于目标值，直接返回 true ；
3. 如果当前元素大于目标值，说明目标值在当前列的左侧，列索引 j-- ；
4. 如果当前元素小于目标值，说明目标值在当前行的下方，行索引 i++ ；
5. 当行索引超出行数或列索引小于0时，说明目标值不存在，返回 false 。
 
这个思路的时间复杂度是O(m+n)，空间复杂度是O(1)，效率远高于暴力遍历。
 
三、C++代码实现
 
cpp
  
#include <vector>
using namespace std;

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        // 处理空数组的情况
        if (matrix.empty() || matrix[0].empty()) return false;
        int m = matrix.size();    // 行数
        int n = matrix[0].size(); // 列数
        int i = 0, j = n - 1;     // 从右上角开始查找
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] > target) {
                j--; // 目标在左侧，列左移
            } else {
                i++; // 目标在下方，行下移
            }
        }
        return false;
    }
};

// 测试示例
int main() {
    vector<vector<int>> matrix = {
        {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}
    };
    Solution s;
    // 测试目标值存在的情况
    bool res1 = s.searchMatrix(matrix, 5);
    // 测试目标值不存在的情况
    bool res2 = s.searchMatrix(matrix, 20);
    return 0;
}
 
 
四、代码解释
 
1. 首先判断数组是否为空，避免访问空数组导致程序崩溃；
2. 定义行索引 i 和列索引 j ，从右上角开始查找；
3. 通过 while 循环不断缩小查找范围，直到找到目标值或遍历完有效范围；
4. 主函数中给出了测试示例，可直接运行验证结果。
 
五、总结
 
这道题的核心是利用二维数组的有序性，选择合适的起始点来减少查找次数。除了从右上角开始，也可以选择左下角作为起始点，思路是类似的。掌握这种“利用数组特性优化查找”的思维，对解决其他算法题也很有帮助。
 
如果觉得这篇文章对你有帮助，欢迎点赞、收藏、关注～如果有其他算法问题，也可以在评论区留言交流！
 
 
 
要不要我帮你给这篇博文加上代码运行结果的截图说明和常见问题解答板块，让内容更完整？