C++二维数组查找：从O(n²)暴力遍历到O(n+M)最优解

栗子

发布时间：2026-10-13 | 3人浏览过

原创

在C++编程与面试中，处理具有特定规律的二维数组是常见考点。本文详细讲解了如何在行列有序的矩阵中查找目标数值，通过对比基础的暴力遍历法与利用边界特性的动态基点法，帮助开发者理解如何通过优化路径将时间复杂度从平方级降至线性对数级。

问题背景与场景

在一个二维整数数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。这类问题常被称为“杨氏矩阵”查找，也是许多互联网技术面试的经典基础题。

假设我们面临以下结构的数据（以4x4为例）：

int arr[4][4] = { 
    {1,2,8,9},
    {2,4,9,12},
    {4,7,10,13},
    {6,8,11,15} 
};

方法一：暴力遍历法

最直观的思路是不顾数据内部的有序性，直接对整个二维数组进行逐行、逐列的扫描。如果发现元素等于目标值，则返回当前位置；若遍历结束仍未找到，则返回未找到。

第1步：编写全量扫描逻辑

使用嵌套 for 循环分别遍历行和列。这种方法虽然逻辑简单，但忽略了数组有序这一关键特征，导致时间复杂度较高。对于大小为 M×N 的数组，其时间复杂度为 O(M×N)。

#include<stdio.h>
// 参数prow和pcol用于回传找到的坐标索引
int search(const int arr[4][4], int num,
           unsigned int* prow, unsigned int* pcol)
{
    int i = 0;
    // 遍历所有行
    for (i = 0; i < *prow; i++)
    {
        int j = 0;
        // 遍历当前行的所有列
        for (j = 0; j < *pcol; j++)
        {
            // 发现目标值，记录坐标并立即返回
            if (arr[i][j] == num)
            {
                *prow = i;
                *pcol = j;
                return 1; // 成功标志
            }
        }
    }
    return 0; // 失败标志
}

适用性说明： 尽管暴力法效率较低，但在数据量极小或数组无序的情况下，这仍然是最稳妥的基础方案。对于应付部分学校基础考试而言，它是合格的实现。

方法二：动态基点优化法

面试官通常期望看到更高效的解法。由于数组具有“行列递增”的性质，我们可以从右上角（或左下角）出发进行搜索。以右上角为基准点时，如果当前值大于目标值，则说明目标值不可能在当前列（因为当前列下方的值更大），可以排除整列；反之，如果当前值小于目标值，则说明目标值不可能在当前行，可以排除整行。

第2步：构建从右上角开始的搜索循环

初始化指针位置为第一行的最后一列（即右上角）。根据比较结果动态调整行下标（增加向下移动）或列下标（减少向左移动）。

这种策略每次都能剔除一行或一列的数据，显著减少了不必要的遍历。对于 M×N 的矩阵，最坏情况下需要走 M + N 步，因此时间复杂度优化为 O(M+N)。

#include<stdio.h>
int search_optimized(const int arr[4][4], int num,
                     unsigned int* prow, unsigned int* pcol)
{
    unsigned int x = 0;          // 起始行
    unsigned int y = *pcol - 1; // 起始列（最后一列，即右上角）

    // 当坐标仍在数组范围内时继续
    while ((x < *prow) && (y >= 0))
    {
        if (arr[x][y] > num)
        {
            // 当前值大于目标值，说明目标值在左侧，左移一列
            y--;
        }
        else if (arr[x][y] < num)
        {
            // 当前值小于目标值，说明目标值在下方，下移一行
            x++;
        }
        else
        {
            // 找到目标值，更新坐标并返回成功
            *prow = x;
            *pcol = y;
            return 1;
        }
    }
    return 0;
}

完整测试逻辑与运行

在实际工程中，建议将搜索逻辑封装为独立函数。主程序负责获取用户输入并调用上述逻辑之一进行验证。

#include<stdio.h>

// ... 此处省略 search 或 search_optimized 函数的具体定义，同上 ...

int main()
{
    int arr[4][4] = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
    int num = 0;

    unsigned int row = sizeof(arr) / sizeof(arr[0]);
    unsigned int col = sizeof(arr[0]) / sizeof(arr[0][0]);

    printf("请输入你想要找的数:");
    scanf("%d", &num);

    // 调用你选择的算法函数，例如 search_optimized
    // 注意：实际使用中建议区分不同函数的接口，避免命名冲突
    if (/* 插入对应的搜索函数调用 */) 
    {
        printf("有这个数\n坐标为(%u,%u)\n", row, col);
    } 
    else 
    {
        printf("没有这个数\n");
    }
    
    return 0;
}