在LeetCode上搜索二维矩阵时堆缓冲区溢出

Question

我正在编写LeetCode问题74的解决方案。搜索二维矩阵:

写一个在m x n矩阵中搜索值的高效算法。这个矩阵有以下属性:

• 每一行的整数从左到右排序。
• 每一行的第一个整数大于前一行的最后一个整数。

下面是我的代码:

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

这是最优解

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;
}
}

Answer 2

问题是您需要i <= n，但i与n无关，而是与m有关。在n > m的情况下，您可能会对matrix[i]执行超出范围的访问，并且您得到的错误消息是该结果。

将i <= n改为i <= m