在Javascript中进行二进制搜索 [英] Binary Search in Javascript

问题描述

我正在尝试在JavaScript中实现二进制搜索算法。事情似乎没问题，但我的回复陈述似乎是未定义的回归？谁能告诉我这里有什么问题？

I'm trying to implement a binary search algorithm in JavaScript. Things seem okay, but my return statements appear to be returning undefined? Can anybody tell what's wrong here?

小提琴： 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);

推荐答案

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

You're not explicitly returning the recursive inner calls (i.e. return binarySearch()), so the call stack unfolds with no return value. Update your code like so:

// ...
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 {
// ...

查看工作小提琴

这篇关于在Javascript中进行二进制搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！