递归二分查找有序数组元素首尾位置的代码问题排查

你的代码存在三个关键问题，导致无法正确获取目标元素的首次出现位置：

1. 未声明局部变量导致全局污染 #

代码中firstOccurence和lastOccurence没有用let或const声明，会自动成为全局变量。在递归调用过程中，不同层级的递归会互相覆盖这些变量的值，导致结果出错。

2. 错误处理递归返回的-1值 #

当你找到目标元素后，递归查找左半部分（寻找更早的出现位置），如果左半部分没有找到目标（返回-1），此时checkFirstOccurence < firstOccurence（即-1 < mid）的条件会成立，错误地将firstOccurence设置为-1。但-1表示左半部分无目标元素，此时首次出现位置应该是当前的mid，而不是-1。

3. 递归返回值类型不统一导致比较失效 #

代码中，当找到目标元素时返回数组[firstOccurence, lastOccurence]，未找到时返回-1。但你直接将递归返回值（可能是数组）与数字比较（比如checkLastOccurence > lastOccurence），数组和数字比较会转换为NaN，导致条件判断完全失效，无法正确更新末次出现位置。

修正后的代码 #

function firstAndLastOccurenceOfElement(arr, key, start, end) {
    // 未找到元素时返回 [-1, -1] 统一返回类型
    if (start > end) {
        return [-1, -1];
    }

    let mid = Math.floor((start + end) / 2);
    let firstOccurence = -1;
    let lastOccurence = -1;

    if (arr[mid] === key) {
        // 当前位置是一个有效出现点
        firstOccurence = mid;
        lastOccurence = mid;
        
        // 递归查找左半部分，获取左半部分的首尾位置
        const leftResult = firstAndLastOccurenceOfElement(arr, key, start, mid - 1);
        if (leftResult[0] !== -1) {
            // 左半部分找到更早的出现位置，更新首次出现
            firstOccurence = leftResult[0];
        }
        // 递归查找右半部分，获取右半部分的首尾位置
        const rightResult = firstAndLastOccurenceOfElement(arr, key, mid + 1, end);
        if (rightResult[1] !== -1) {
            // 右半部分找到更晚的出现位置，更新末次出现
            lastOccurence = rightResult[1];
        }
        return [firstOccurence, lastOccurence];
    } else if (arr[mid] > key) {
        // 目标在左半部分，直接返回左半部分的结果
        return firstAndLastOccurenceOfElement(arr, key, start, mid - 1);
    } else {
        // 目标在右半部分，直接返回右半部分的结果
        return firstAndLastOccurenceOfElement(arr, key, mid + 1, end);
    }
}

let arr = [2, 5, 5, 5, 6, 6, 8, 9, 9, 9];
let key = 5;
console.log(firstAndLastOccurenceOfElement(arr, key, 0, arr.length - 1)); // 输出 [1, 3]

修正要点说明 #

• 统一返回值类型：未找到元素时返回[-1, -1]，避免数组与数字的错误比较。
• 声明局部变量firstOccurence和lastOccurence，避免全局污染。
• 递归调用后先判断返回的首尾位置是否有效（不为-1），再更新当前的首尾位置。
• 简化分支判断逻辑，让代码更清晰。

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