Javascript 中的二进制搜索

Question

我正在尝试在 JavaScript 中实现二进制搜索算法。事情似乎没问题，但我的返回语句似乎返回未定义。谁能告诉我这里出了什么问题？

小提琴：http: //jsfiddle.net/2mBdL/

 var a = [
    1,
    2,
    4,
    6,
    1,
    100,
    0,
    10000,
    3
];

a.sort(function (a, b) {
    return a - b;
});

console.log('a,', a);

function binarySearch(arr, i) {
    var mid = Math.floor(arr.length / 2);
    console.log(arr[mid], i);

    if (arr[mid] === i) {
        console.log('match', arr[mid], i);
        return arr[mid];
    } else if (arr[mid] < i && arr.length > 1) {
        console.log('mid lower', arr[mid], i);
        binarySearch(arr.splice(mid, Number.MAX_VALUE), i);
    } else if (arr[mid] > i && arr.length > 1) {
        console.log('mid higher', arr[mid], i);
        binarySearch(arr.splice(0, mid), i);
    } else {
        console.log('not here', i);
        return -1;
    }

}
var result = binarySearch(a, 100);
console.log(result);

原文由 4m1r 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您没有明确返回递归内部调用（即 return binarySearch() ），因此调用堆栈展开时没有返回值。像这样更新您的代码：

 // ...
if (arr[mid] === i) {
    console.log('match', arr[mid], i);
    return arr[mid];
} else if (arr[mid] < i && arr.length > 1) {
    console.log('mid lower', arr[mid], i);
    return binarySearch(arr.splice(mid, Number.MAX_VALUE), i);
} else if (arr[mid] > i && arr.length > 1) {
    console.log('mid higher', arr[mid], i);
    return binarySearch(arr.splice(0, mid), i);
} else {
// ...

查看 工作小提琴

原文由 Eliran Malka 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

以这样一种方式编写搜索函数很有用：如果未找到元素，它会返回一个负值，指示新元素的插入点。此外，在二分搜索中使用递归是过度且不必要的。最后，通过提供比较器函数作为参数使搜索算法具有通用性是一种很好的做法。下面是实现。

 function binarySearch(ar, el, compare_fn) {
    var m = 0;
    var n = ar.length - 1;
    while (m <= n) {
        var k = (n + m) >> 1;
        var cmp = compare_fn(el, ar[k]);
        if (cmp > 0) {
            m = k + 1;
        } else if(cmp < 0) {
            n = k - 1;
        } else {
            return k;
        }
    }
    return -m - 1;
}

此代码 在此处 带有注释和单元测试。

原文由 Alexander Ryzhov 发布，翻译遵循 CC BY-SA 3.0 许可协议