二分查找实现报错排查：仅16/36用例通过，请求定位错误

任务 #

实现二分查找算法。

输入格式 #

• 第一行输入整数𝑛
• 第二行是𝑛个严格递增的互不相同正整数序列𝑎₀ < 𝑎₁ < ... < 𝑎ₙ₋₁
• 第三行输入整数k
• 第四行是𝑘个正整数𝑏₀, 𝑏₁, ..., 𝑏ₖ₋₁

约束条件 #

• 1 ≤ 𝑛, 𝑘 ≤ 10^4
• 1 ≤ 𝑎ᵢ ≤ 10^9（0 ≤ 𝑖 < 𝑛）
• 1 ≤ 𝑏ⱼ ≤ 10^9（0 ≤ 𝑗 < 𝑘）

输出格式 #

对每个𝑏ᵢ（0 ≤ 𝑖 < 𝑘），输出其在数组𝑎中的索引𝑗（0 ≤ 𝑗 ≤ 𝑛-1），不存在则输出-1。

问题现状 #

代码仅通过16/36测试用例，第17用例报Wrong answer，运行时间0.06/5.00，内存占用46145536/536870912。

原代码 #

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    terminal: false
});

process.stdin.setEncoding('utf8');
rl.once('line', line => {
    const n = parseInt(line, 10);
    rl.once('line', line => {
        let arr;
        if (line.toString() === '') {
            arr = [];
        } else {
            arr = line.toString().split(' ').slice(0, n).map(Number);
        }

        rl.once('line', line => {
            const k = parseInt(line, 10);

            rl.once('line', line => {
                const keys = line.toString().split(' ').map(Number);
                const result = [];

                for (let i = 0; i < k; i++) {
                    result.push(binarySearch(arr, keys[i]));
                }

                const res = result.join(' ');
                const maxLength = 50000;

                for (let i = 0; i < res.length; i += maxLength) {
                    process.stdout.write(res.slice(i, i + maxLength));
                }

                process.stdout.write('\n');
                process.exit();
            })
        })
    })
});

function binarySearch(arr, key) {
    if (arr.length === 0) return -1;
    let l = 0;
    let r = arr.length - 1;
    let m;
    while (l <= r) {
        m = Math.ceil((l + r) / 2);
        if (arr[m] === key) {
            return m;
        }
        if (arr[m] > key) r = m - 1;
        if (arr[m] < key) l = m + 1;
    }
    return -1;
}

错误分析与修复方案 #

1. 二分查找中点计算错误 #

原代码使用Math.ceil((l + r)/2)向上取整计算中点，会在部分边界场景下导致死循环或漏查。正确的二分查找应该使用向下取整计算中点，确保区间收缩逻辑正确。

修复后的binarySearch函数：

function binarySearch(arr, key) {
    let l = 0;
    let r = arr.length - 1;
    while (l <= r) {
        // 向下取整计算中点，避免边界逻辑错误
        const m = Math.floor((l + r) / 2);
        if (arr[m] === key) {
            return m;
        } else if (arr[m] > key) {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return -1;
}

2. 输入处理未截断多余元素 #

原代码处理第四行输入时，未截取前k个元素，若输入元素数量超过k，会导致输出结果数量不符合题目要求，触发Wrong answer。

修复输入处理逻辑，对keys数组截取前k个元素：

const keys = line.toString().split(' ').slice(0, k).map(Number);

简化冗余逻辑 #

根据约束条件n≥1，第二行不可能为空，可直接删除空行判断逻辑，简化代码。输出部分用console.log替代分块写入，更简洁且能满足需求。

修复后完整代码 #

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    terminal: false
});

process.stdin.setEncoding('utf8');
rl.once('line', line => {
    const n = parseInt(line, 10);
    rl.once('line', line => {
        const arr = line.toString().split(' ').slice(0, n).map(Number);

        rl.once('line', line => {
            const k = parseInt(line, 10);

            rl.once('line', line => {
                const keys = line.toString().split(' ').slice(0, k).map(Number);
                const result = [];

                for (let i = 0; i < k; i++) {
                    result.push(binarySearch(arr, keys[i]));
                }

                console.log(result.join(' '));
                process.exit();
            })
        })
    })
});

function binarySearch(arr, key) {
    let l = 0;
    let r = arr.length - 1;
    while (l <= r) {
        const m = Math.floor((l + r) / 2);
        if (arr[m] === key) {
            return m;
        } else if (arr[m] > key) {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    return -1;
}

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