不使用额外空间合并有序数组提交GeeksforGeeks出现垃圾值问题

你的代码触发了数组越界的未定义行为，不同平台的内存布局差异导致本地运行正常、GFG平台随机出现垃圾值：

• 第一个bug：binary_search函数存在越界访问。你将high初始化为传入的长度n，循环中直接访问a[mid+1]，当mid等于n时，会访问数组的越界位置，读取到不确定的脏数据。
• 第二个bug：调用二分查找时传参错误。数组b的长度是m，但你调用binary_search时第二个参数始终传和n相关的值，完全没有用到m参数，直接超出b数组的合法访问范围。
• 第三个bug：swap循环的条件逻辑错误。你用了||作为循环判断条件，只要满足一个就继续执行，会出现其中一个下标已经超出合法范围的情况，再次触发越界读写。

首先修正二分查找逻辑，避免越界同时正确返回小于目标值的最后一个下标：

void swap(int* a,int* b)
{
    int temp=*a;
    *a=*b;
    *b=temp;
}

// 返回a数组中最后一个小于k的元素下标，没有小于k的元素返回-1
int binary_search(int a[],int len,int k)
{
    int low=0;
    int high=len-1;
    int res = -1;
    while(high>=low)
    {
        int mid = low + (high - low)/2; // 避免整数溢出
        if(a[mid] < k)
        {
            res = mid;
            low=mid+1;
        }
        else
        {
            high=mid-1;
        }
    }
    return res;
}

然后修正merge函数的参数传递和循环逻辑：

class Solution{
public:
    void merge(int a[], int b[], int n, int m) {
        int pos = m-1; // 初始为b数组的最后一个下标
        for(int i=n-1;i>=0;--i)
        {
            pos = binary_search(b, m, a[i]); // 正确传入b数组的长度m
            int smaller = pos+1;
            
            if(smaller > n-i)
                continue;
                
            int j,k;
            // 改用&&保证两个下标都在合法范围内
            for(j=0,k=n-1;j<smaller && k>=i;++j,--k)
            {
                swap(&b[j],&a[k]);
            }
            break;
        }
        sort(a,a+n);
        sort(b,b+m);
    }
};

当前实现最后调用两次排序的时间复杂度为O(nlogn + mlogm)，如果需要更高效率，可以使用标准的双指针从后往前遍历的解法，无需最后排序，时间复杂度可以降到O(n+m)。

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