二分插入算法递归实现中数组后半段未被递归调用问题排查

问题根因：全局变量污染 #

你代码中的output、halflength_floor、halflength_ceil、first、second变量均未使用var/let/const声明，默认挂载到全局作用域，导致变量值被后续执行逻辑覆盖：

1. 初始调用insertNum(7,[2,3,5,6,8])时，调用splitInHalf给全局output赋值为{first: [2,3], second: [5,6,8]}
2. 执行insertNum(7,output.first)（即处理子数组[2,3]）时，内部再次调用splitInHalf，直接修改了全局output的值为{first: [2], second: [3]}
3. 等insertNum(7,[2,3])执行完成，要执行concat中的第二个insertNum调用时，output.second已经被覆盖为3，而非初始的[5,6,8]，因此永远不会执行你预期的[5,6,8]子数组处理逻辑，最终得到错误结果。

修复方案 #

给所有局部变量添加作用域声明，避免全局污染，同时你用来存储拆分结果的output本质是键值对结构，用对象比数组更合理：

function insertNum(num,sortedSet){
    var returnValue;
    console.log(`sortedSet:${sortedSet}`);
    if (sortedSet.length==0){
        return [num];
    }
    if(sortedSet.length>1){
        console.log('length greater than 1');
        // 给output添加var声明，变成局部变量
        var output=splitInHalf(sortedSet);
        if(num>output.first[output.first.length-1]&&num<output.second[0]){
            console.log(`${num} belongs between`)
            return output.first.concat([num]).concat(output.second);
        }
        else{
            return insertNum(num,output.first).concat(insertNum(num,output.second));
        }
    }
    else{
        if(num==sortedSet[0]){
            returnValue=[num,sortedSet[0]]
            console.log(`returning append:${returnValue}`);
            return returnValue;
        }
        else{
            return sortedSet;
        }
    }
}

function splitInHalf(sortedSet){
    // 所有变量添加const声明，变成局部变量
    const halflength_floor=Math.floor(sortedSet.length/2);
    const halflength_ceil=Math.ceil(sortedSet.length/2);
    console.log(`halflength_floor:${halflength_floor}`);
    console.log(`halflength_ceil:${halflength_ceil}`);
    const first=sortedSet.slice(0,halflength_floor);
    const second=sortedSet.slice(halflength_floor);
    console.log(`first:${first}`);
    console.log(`second:${second}`);
    // 用对象存储键值对更符合使用场景
    const output={};
    output.first=first;
    output.second=second;
    return output;
}

console.log(insertNum(7,[2,3,5,6,8]));

修复后运行会输出预期结果[2, 3, 5, 6, 7, 8]。

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