LeetCode 上 Search a 2D Matrix 中的堆缓冲区溢出

Question

我正在编写 LeetCode 问题的解决方案 74. Search a 2D Matrix:

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.

The first integer of each row is greater than the last integer of the previous row.

这是我的代码：

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int m=matrix.size()-1, n= matrix[0].size()-1;
    int i=0, j=n;
    int small=matrix[0][0], large=matrix[m][n];
    if(target<small || target>large)return false;
    
    while(i<=n && j>=0){
        if(target==matrix[i][j])return true;
        if(target<matrix[i][j])j--;
        else i++;
    }
    return false;
}

这段代码运行对于很多情况都很好，但对于这个测试用例却失败了：

输入：
```
[[-1,3]]
1
```
预期输出：false

我的输出：

=================================================================
==29==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x603000000778 at pc 0x000000345efd bp 0x7ffc1c1fc3f0 sp 0x7ffc1c1fc3e8
READ of size 8 at 0x603000000778 thread T0
    #4 0x7fc2b36c60b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x603000000778 is located 0 bytes to the right of 24-byte region [0x603000000760,0x603000000778)
allocated by thread T0 here:
    #6 0x7fc2b36c60b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c067fff8090: fa fa fd fd fd fd fa fa fd fd fd fa fa fa fd fd
  0x0c067fff80a0: fd fd fa fa fd fd fd fd fa fa fd fd fd fd fa fa
  0x0c067fff80b0: fd fd fd fd fa fa fd fd fd fa fa fa fd fd fd fa
  0x0c067fff80c0: fa fa fd fd fd fa fa fa fd fd fd fa fa fa fd fd
  0x0c067fff80d0: fd fa fa fa fd fd fd fa fa fa fd fd fd fa fa fa
=>0x0c067fff80e0: fd fd fd fa fa fa fd fd fd fa fa fa 00 00 00[fa]
  0x0c067fff80f0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff8100: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff8110: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff8120: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c067fff8130: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==29==ABORTING

我这里缺少哪个条件？

Answer 1

问题是你需要i <= n，但是i与n无关，而是与m无关。在 n > m 的情况下，您可能会执行对 matrix[i] 的超出范围的访问，而您收到的错误消息就是由此产生的结果。

因此将 i <= n 更改为 i <= m。

Answer 2

这是最好的最优解

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        
        if(!matrix.size()){
            return false;
        }
        int n = matrix.length;
        int m = matrix[0].length;
        
        int a=0;
        int b = (n*m)-1;
        **// Binary Search** 
        while(a<=b){
            int c = (a+(b-a)/2);
            if(matrix[c/m][c%m] == target){
                return true;
            }
            if(matrix[c/m][c%m] <target){
                a = c+1;
            }
            else{
                b = c-1;
            }
        }
        return false;
    }
}

LeetCode 上 Search a 2D Matrix 中的堆缓冲区溢出

Heap buffer overflow in Search a 2D Matrix on LeetCode

c++

buffer

2d

heap-memory