求解有序数组limits各元素在有序数组punct_arr中的最近值

原有代码的问题 #

• 索引越界：循环中访问punct_arr[punct - 1]时，punct初始值为0，会拿到不存在的-1索引；访问limits[limit + 1]时，当遍历到limits最后一个元素也会越界
• 逻辑完全错误：判断条件和「找最接近元素」的需求无关，且多次匹配会重复push元素，最终结果长度会超过limits数组长度
• 效率低下：两个数组均为有序状态，完全不需要用O(n*m)的双层循环实现

最优实现方案 #

因为两个数组均为升序有序，推荐用二分查找实现，时间复杂度为O(m log n)（m是limits长度，n是punct_arr长度），思路如下：
对每个limits[i]，先找到它在punct_arr中第一个大于等于自身的插入位置pos，此时最接近的元素只可能是pos前一位（pos-1）或pos位置的元素，处理边界情况后对比差值选择即可。

可直接运行的代码： #

function getSeparationIndex(limits, punct_arr) {
    const separation_index = [];
    for (const target of limits) {
        let left = 0, right = punct_arr.length;
        // 二分找插入位置
        while (left < right) {
            const mid = (left + right) >> 1;
            if (punct_arr[mid] < target) left = mid + 1;
            else right = mid;
        }
        const pos = left;
        // 处理边界：插入位置在最开头，直接选第一个元素
        if (pos === 0) {
            separation_index.push(punct_arr[0]);
        }
        // 处理边界：插入位置在最末尾，直接选最后一个元素
        else if (pos === punct_arr.length) {
            separation_index.push(punct_arr[punct_arr.length - 1]);
        }
        // 对比前后两个元素的差值，选更小的
        else {
            const diffPrev = Math.abs(target - punct_arr[pos - 1]);
            const diffCurr = Math.abs(target - punct_arr[pos]);
            separation_index.push(diffPrev <= diffCurr ? punct_arr[pos - 1] : punct_arr[pos]);
        }
    }
    return separation_index;
}

// 测试示例
const limits = [280, 560];
const punct_arr = [5, 99, 151, 159, 255, 352, 462, 502, 519, 531, 556, 602];
console.log(getSeparationIndex(limits, punct_arr)); // 输出 [255, 556] 符合预期

如果两个数组均为升序，还可以用双指针法实现O(n+m)的时间复杂度，适合数据量极大的场景：

function getSeparationIndex(limits, punct_arr) {
    const separation_index = [];
    let punctPtr = 0;
    const n = punct_arr.length;
    for (const target of limits) {
        // 指针移到第一个大于等于target的位置
        while (punctPtr < n && punct_arr[punctPtr] < target) {
            punctPtr++;
        }
        // 和二分逻辑一致判断选前一个还是当前
        if (punctPtr === 0) {
            separation_index.push(punct_arr[0]);
        } else if (punctPtr === n) {
            separation_index.push(punct_arr[n - 1]);
        } else {
            const diffPrev = Math.abs(target - punct_arr[punctPtr - 1]);
            const diffCurr = Math.abs(target - punct_arr[punctPtr]);
            separation_index.push(diffPrev <= diffCurr ? punct_arr[punctPtr - 1] : punct_arr[punctPtr]);
        }
    }
    return separation_index;
}

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