有序二维矩阵中目标值搜索方案的效率咨询

嘿，先给你的思路点个赞——用两次独立循环代替嵌套遍历，还加了提前的边界判断，逻辑清晰又避免了最暴力的O(n*m)写法，这点做得很棒！不过咱们得从时间复杂度的角度，好好唠唠它算不算“高效实现”。

你的方案的效率拆解 #

先算一下时间开销：

• 第一个循环定位目标行：最坏情况得遍历完所有行（比如target刚好在最后一行），时间是O(rowL)
• 第二个循环在目标行找元素：最坏情况得遍历整行，时间是O(colL)
• 总时间复杂度是O(rowL + colL)，空间上只用了几个变量，是O(1)的，属于线性时间的实现。

这个实现对付小规模矩阵完全够用，但如果碰到超大矩阵（比如1万行×1万列），线性时间的开销就会比对数时间的实现大不少——毕竟log(1e8)也就27步左右，和2万步的差距还是很明显的。

更高效的优化思路 #

因为题目里的矩阵是每行从左到右递增，每列从上到下也递增，而且下一行的第一个元素比上一行最后一个元素大，咱们可以利用这个严格的有序性，实现对数级时间的搜索：

思路1：把矩阵当成一维有序数组做二分查找 #

矩阵的总元素数是rowL * colL，咱们可以把二维坐标转换成一维索引：

• 一维索引idx对应的二维位置是：行号idx / colL，列号idx % colL
  这样就能直接用标准的二分查找，时间复杂度降到O(log(rowL*colL))，也就是O(log rowL + log colL)，比线性时间高效太多。

给你贴个示例代码：

public boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int left = 0;
    int right = rows * cols - 1;

    while (left <= right) {
        // 避免溢出的mid计算方式
        int mid = left + (right - left) / 2;
        int midValue = matrix[mid / cols][mid % cols];
        if (midValue == target) {
            return true;
        } else if (midValue < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

思路2：双指针法（代码更简洁，但时间复杂度和你的方案一致） #

从矩阵的右上角（或者左下角）开始遍历：

• 如果当前元素等于target，直接返回true
• 如果当前元素比target大，往左走一列（因为下方的元素只会更大，不可能在这一列找到target）
• 如果当前元素比target小，往下走一行（因为左边的元素只会更小，不可能在这一行找到target）
  这个方法的时间复杂度还是O(rowL + colL)，但代码更简洁，可读性也不错。

示例代码：

public boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    int row = 0;
    int col = cols - 1;

    while (row < rows && col >= 0) {
        if (matrix[row][col] == target) {
            return true;
        } else if (matrix[row][col] > target) {
            col--;
        } else {
            row++;
        }
    }
    return false;
}

最后总结你的方案 #

你的实现属于合格、易读的线性时间解法，但不算最优的高效实现。如果矩阵规模不大，你的写法完全没问题，而且逻辑简单好维护；但如果要处理超大矩阵，或者追求最优时间复杂度，二分查找的方案会更合适。

内容的提问来源于stack exchange，提问作者kmvfkmfv