javascript - Javascript 中的二进制搜索

Question

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

fiddle :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);

Answer 1

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

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;
}

此代码带有注释和单元测试 here .