力扣搜索二维数组出现的问题

如图，使用二分查找出现如下报错，请问这是怎么产生的，应该怎么解决

题主，你要二分查找法解题，若有帮助，还望采纳，点击回答右侧采纳即可。

思路：这种二维问题，首先想到动态规划， 如果统计找到某个值的步数，直接dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; 可以先找到所在行，然后在二分查找。

解题方法：先遍历每行，再用二分查找

时间复杂度: O(mlogn)
空间复杂度: O(l)

解题代码如下，请参考一下。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size(), n = matrix[0].size();
        int i = 0;
        //遍历每一行
        while(i < m){
            //查找target所在区间
            if(matrix[i][0] <= target && matrix[i][n - 1] >= target){
                //二分查找
                int left = 0, right = n - 1;
                while(left <= right){
                    int mmm = left + (right - left) / 2;
                    if(target > matrix[i][mmm]){
                        left = mmm+1;
                    }else if(target < matrix[i][mmm]){
                        right = mmm-1;
                    }else{
                        return true;
                    }
                }
            }   
            i++;
        }
        return false;
    }
};

提交截图：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int row = -1;
        
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] <= target && matrix[i][n-1] >= target) {
                row = i;
                break;
            }
        }
        
        if (row == -1) return false;
        
        int left = 0;
        int right = n - 1;
        
        while (left <= right) {
            int middle = left + (right - left) / 2;
            
            if (matrix[row][middle] == target) {
                return true;
            } else if (matrix[row][middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        
        return false;
    }
};

for循环的条件应该是i < m - 1，而不是i < m。因为当i = m - 1时，matrix[i + 1][o]会访问到数组越界的位置。所以会报这个异常。
修改后的代码如下：

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int row;
        int m = matrix.size();
        int n = matrix[0].size();
        for (int i = 0; i < m - 1; i++) {
            if (matrix[i][n - 1] <= target || matrix[i + 1][n - 1] > target) {
                row = i;
                break;
            }
        }
        int left = 0;
        int right = matrix[row][n - 1];
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (matrix[row][middle] < target) {
                left = middle + 1;
            } else if (matrix[row][middle] > target) {
                right = middle - 1;
            } else if (matrix[row][middle] == target) {
                return true;
            }
        }
        return false;
    }
};

如果以上回答对您有所帮助，点击一下采纳该答案～谢谢

数组越界了，你看看那个for循环

引用 皆我百晓生 小程序回复内容作答：
这个错误是因为你的代码在访问一个地址错误的内存位置，导致出现了未定义行为。具体来说，这个错误是在 stl_vector.h 文件的第 1043 行发生的。

你可以尝试以下的方法来解决这个问题：

1. 确保你的二分查找算法没有越界访问数组。请检查你的索引计算是否正确，以及查看数组的边界情况。
2. 确保你的二维数组是正确初始化的，并且没有出现内存错误。可以使用 std::vector 或动态分配内存来创建二维数组。
3. 检查其他部分的代码，看是否存在其他潜在的内存错误，比如使用已经被释放的内存指针或者越界访问。

如果你能提供更多的代码和问题的上下文，我会尽力提供更准确的帮助。

【以下回答由 GPT 生成】

这个报错是由于数组访问越界导致的。具体来说，是因为在以下代码中：

if (matrix[i][n] <= target && matrix[i + 1][0] > target) {

当i等于m-1时，i+1会超出矩阵的索引范围，导致访问了一个不存在的行。这就是报错的原因。

为了修复这个问题，你需要在遍历矩阵时，将for循环的终止条件由i < m改为i < m-1。这样，在最后一次迭代时，即i=m-2时，就不会访问不存在的行，也就不会产生越界报错了。

以下是修复后的代码：

public bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m = matrix.size();
    int n = matrix[0].size();

    for (int i = 0; i < m-1; i++) {
        if (matrix[i][n-1] <= target && matrix[i + 1][0] > target) {
            int row = i;
            int left = 0;
            int right = matrix[row][n - 1];

            while (left <= right) {
                int middle = left + (right - left) / 2;
                if (matrix[row][middle] > target)
                    right = middle - 1;
                else if (matrix[row][middle] < target)
                    left = middle + 1;
                else if (matrix[row][middle] == target)
                    return true;
            }
        }
    }
    return false;
}

修复后的代码应该就能正常运行了。希望对你有帮助！如果还有其他问题，请随时提问。

【相关推荐】

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7628696
• 这篇博客你也可以参考下：力扣：在二维数组中的查找某个数，笔记记录
• 您还可以看一下 孙玖祥老师的图解数据结构与算法课程中的 字符串暴力匹配算法及实现小节, 巩固相关知识点
  
• 除此之外, 这篇博客: 导图整理数组1: 总结了二分查找的通用模板写法, 彻底解决几个易混淆问题, 力扣35:搜索插入位置中的 3.循环退出条件 部分也许能够解决你的问题。