矩阵搜索代码无法运行：如何修正该程序使其正常执行？

原代码存在的问题 #

• 数组越界访问：代码直接访问matrix[i][j+1]和matrix[i+1][j]，但未提前检查j+1是否小于当前行的列数、i+1是否小于矩阵的行数。当处于最后一行或最后一列时，这类访问会触发未定义行为，导致程序崩溃。
• 逻辑判断错误：判断条件不符合矩阵的特性——矩阵每行非递减，且下一行首元素大于当前行尾元素。原代码中matrix[i][j+1]<=target and matrix[i+1][j]>target的逻辑完全不成立，因为matrix[i+1][j]是下一行的首元素，必然大于当前行的所有元素（包括matrix[i][j+1]），这个条件永远无法满足，导致j永远不会递增。
• 冗余判断：while循环的条件已经限制了i<matrix.size()和j<matrix[0].size()，循环内部再次判断i>=matrix.size() or j>=matrix[0].size()完全多余。
• 遍历逻辑缺陷：从(0,0)开始逐个移动的方式既低效，又可能漏掉target的位置，无法正确定位到目标元素。

修正方案 #

利用矩阵的有序特性，我们可以选择两种高效的实现方式：

方案一：一维二分查找 #

将整个矩阵视为一个连续的一维有序数组，通过索引映射实现二分查找，时间复杂度为O(log(mn))：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int rows = matrix.size();
        int cols = matrix[0].size();
        int left = 0, right = rows * cols - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 将一维索引转换为二维坐标
            int val = matrix[mid / cols][mid % cols];
            if (val == target) {
                return true;
            } else if (val < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
};

方案二：先定位行，再行内查找 #

先通过行首和行尾元素锁定可能存在target的行，再在该行内遍历查找（行内也可改用二分查找进一步优化）：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int rows = matrix.size();
        int cols = matrix[0].size();
        int targetRow = -1;
        
        // 定位目标行
        for (int i = 0; i < rows; ++i) {
            if (matrix[i][0] <= target && matrix[i].back() >= target) {
                targetRow = i;
                break;
            }
        }
        if (targetRow == -1) return false;
        
        // 在目标行内查找
        for (int num : matrix[targetRow]) {
            if (num == target) return true;
            // 行内非递减，超过target可提前退出
            if (num > target) return false;
        }
        return false;
    }
};

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