javascript - 我可以获得有关二分搜索实现失败的反馈吗？

Question

我的目标是编写一个 indexOf 函数，它使用二分搜索来查找数组中所需元素的索引。

我的问题是，在编写递归解决方案时，我总是会破坏调用堆栈——即使是在绝对很小的数组中。我的期望是，即使在非尾部调用优化的语言中，二分搜索也不应该破坏任何不是巨大大的数组的调用堆栈。

用英语/伪代码来说，我的想法是

• 获取一个 SeedValue 和一个 arrayToSearch
• 设 middle 为数组长度除以 2，向下舍入
• 让 currentValue 为数组中间的任何内容(又名 arrayToSearch[middle]
• 如果currentValue与seekValue相同，则返回middle
• 如果 currentValue 小于 SeedValue，则在此数组的后半部分递归调用此函数
• 如果 currentValue 大于 SeedValue，则在此数组的前半部分递归调用此函数
• 最终我们将得出正确的值并返回它

这是我用 JS 编写的:

function indexOf(soughtValue, arrayToSearch) {
    let middle = Math.floor(arrayToSearch.length / 2);
    let currentValue = arrayToSearch[middle];
    if (soughtValue === currentValue) {
        return middle;
    } else if (soughtValue > currentValue) {
        return indexOf(soughtValue, arrayToSearch.slice(middle, arrayToSearch.length));
    } else if (soughtValue < currentValue) {
        return indexOf(soughtValue, arrayToSearch.slice(0, middle));
    }
}

let x = indexOf("Sarah", ["Jennifer", "Sarah", "David", "Jon"]);
console.log(x); // expecting 1

但是正如我之前所说，堆栈溢出。

我仔细地重新阅读了教科书对二分搜索的解释，并且查阅了哈佛关于该算法的 CS 简介讲座。我相信我理解它的想法，并且我相当有信心 JavaScript 正在做我期望的事情。我了解堆栈溢出的概念以及为什么递归算法可能会触发堆栈溢出。

然而，一遍又一遍地重新阅读我的代码，我无法发现我搞砸并犯了逻辑错误的地方。

如果有人能启发我，我将非常感激，因为我在这里完全耗尽了自己的精神资源，却一无所获。

Answer 1

根据我上面的评论，这是一个完整的工作示例。重大变化:

1. 我没有对数组进行切片，而是使用 start 和 end 索引传递原始数组。这是确保您返回的索引是原始数组中的索引的一种方法。
2. 当我递归时，我确保中间元素不包含在递归调用中。
3. 我有一个基本情况，当我们搜索的数组部分为空时，它会返回 -1 (就像大多数内置 indexOf 实现的行为) .

当然，根据我的第一条评论，我从排序数组开始，因为二分搜索仅适用于排序输入。

function indexOf(soughtValue, arrayToSearch, start=0, end=(arrayToSearch.length-1)) {
    // base case for an empty array or otherwise failing to find the element
    if (start > end) {
        return -1;
    }

    let middle = start + Math.floor((end - start) / 2);
    let currentValue = arrayToSearch[middle];

    if (soughtValue === currentValue) {
        return middle;
    } else if (soughtValue > currentValue) {
        return indexOf(soughtValue, arrayToSearch, middle + 1, end);
    } else if (soughtValue < currentValue) {
        return indexOf(soughtValue, arrayToSearch, start, middle - 1);
    }
}

let input = ["David", "Jennifer", "Jon", "Sarah"];
console.log(indexOf("David", input)); // 0
console.log(indexOf("Jennifer", input)); // 1
console.log(indexOf("Jon", input)); // 2
console.log(indexOf("Sarah", input)); // 3
console.log(indexOf("NOT THERE", input)); // -1

更新

仅供引用，这样的函数可以轻松地迭代编写，而不是使用递归。在这种情况下，我想我更喜欢迭代版本:

function indexOf(soughtValue, arrayToSearch) {
    let start = 0;
    let end = arrayToSearch.length - 1;

    while (start <= end) {
        let middle = start + Math.floor((end-start) / 2);
        let currentValue = arrayToSearch[middle];

        if (soughtValue > currentValue) {
            start = middle + 1;
        } else if (soughtValue < currentValue) {
            end = middle - 1;
        } else {
            return middle;
        }
    }

    // not found
    return -1;
}

let input = ["David", "Jennifer", "Jon", "Sarah"];
console.log(indexOf("David", input)); // 0
console.log(indexOf("Jennifer", input)); // 1
console.log(indexOf("Jon", input)); // 2
console.log(indexOf("Sarah", input)); // 3
console.log(indexOf("NOT THERE", input)); // -1