旋转有序数组搜索代码触发AddressSanitizer堆溢出错误求助

问题场景 #

在解决LeetCode旋转有序数组搜索问题时，编写了如下C++代码，本地运行正常，但提交后触发AddressSanitizer的heap-buffer-overflow错误。

提交的代码 #

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n=nums.size();
        int i=0, low, high;
        int pos=-1;
        while(nums[i]<nums[i+1])
            i++;
        //i stores the index of max element of the array
        if(target<nums[0]) {
            low = i+1;
            high = n-1;
        }
        else {
            low = 0;
            high = i;
        }
        while(low<=high) {
            int mid = (low+high)/2;
            // cout<<low<<high<<mid<<target;
            // cout<<(nums[mid]==target);
            if(nums[mid] == target){
                pos = mid;
                // flag=1;
                break;
            }
            else if(nums[mid]<target) {
                low = mid+1;
            }
            else {
                high = mid-1;
            }
        }
        // if (flag==0)
        //     return -1;
        return pos;
    }
};

错误日志 #

=================================================================
==31==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000194 at pc 0x000000345587 bp 0x7fff5346e5a0 sp 0x7fff5346e598
READ of size 4 at 0x602000000194 thread T0
    #2 0x7f210b53a0b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x602000000194 is located 0 bytes to the right of 4-byte region [0x602000000190,0x602000000194)
allocated by thread T0 here:
    #6 0x7f210b53a0b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff8000: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa
  0x0c047fff8010: fa fa fd fd fa fa fd fa fa fa fd fa fa fa fd fa
  0x0c047fff8020: fa fa fd fa fa fa fd fd fa fa fd fa fa fa fd fa
=>0x0c047fff8030: fa fa[04]fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8060: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8070: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8080: 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
==31==ABORTING

错误原因分析 #

heap-buffer-overflow错误源于访问了数组边界外的内存，问题出在这段循环逻辑：

while(nums[i]<nums[i+1])
    i++;

• 当输入数组是**完全升序（无旋转）**时，i会持续递增到n-1，此时i+1等于数组长度n，访问nums[i+1]就会越界，触发内存访问错误。
• 当数组长度为1时，i+1等于1，同样会越界访问nums[1]，这也是一个潜在的越界场景。

修复方案 #

给循环添加边界条件，确保i+1不超过数组的有效索引范围：

while(i < n-1 && nums[i] < nums[i+1])
    i++;

这样当i到达数组倒数第二个元素时，循环会自动停止，避免访问超出数组范围的内存。

另外，可以额外处理空数组的情况，同时优化二分查找的mid计算方式，避免整数溢出：

修复后的完整代码 #

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n=nums.size();
        if(n == 0) return -1; // 处理空数组特殊情况
        int i=0, low, high;
        int pos=-1;
        while(i < n-1 && nums[i] < nums[i+1])
            i++;
        //i stores the index of max element of the array
        if(target < nums[0]) {
            low = i+1;
            high = n-1;
        }
        else {
            low = 0;
            high = i;
        }
        while(low <= high) {
            int mid = low + (high - low)/2; // 避免low+high溢出
            if(nums[mid] == target){
                pos = mid;
                break;
            }
            else if(nums[mid] < target) {
                low = mid+1;
            }
            else {
                high = mid-1;
            }
        }
        return pos;
    }
};

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