我可以得到反馈我失败的二进制搜索实现

Can I get feedback on my failed binary search implementation?

本文关键字：二进制 搜索 实现 失败 我可以      更新时间：2023-09-26

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

我的问题是，在编写递归解决方案时，我总是破坏调用堆栈——即使是在非常小的数组中。我的期望是，即使在非尾部调用优化的语言中，二进制搜索也不应该破坏任何数组的调用堆栈，这些数组不是大得可怕。

在英语/伪代码中，我的想法是
  • 取一个searchvalue和一个arrayToSearch
  • 设middle为数组的长度除以2，四舍五入
  • 让currentValue是任何在数组的中间(即arrayToSearch[middle]
    • )
  • 如果currentValue与sotvalue相同，返回middle
  • 如果currentValue小于sotvalue，则在该数组的后半部分递归调用此函数
  • 如果currentValue大于sotvalue，递归地在数组的前半部分调用this函数
  • 最终我们会找到正确的值并返回

我是这样用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

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

我仔细重读了课本上关于二分搜索的解释，并查找了哈佛计算机科学入门课程中关于二分搜索算法的讲座。我相信我理解了它的思想，我相信JavaScript正在做我期望它做的事情。我理解堆栈溢出的概念，以及为什么递归算法可能触发堆栈溢出。

然而，一遍又一遍地重读我的代码，我找不到我搞砸的地方，也找不到逻辑错误。

如果有人能给我开导，我将非常感激，因为我已经耗尽了自己的脑力资源，却一无所获。

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

  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

相关文章：