Binary Search in Javascript

Question

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?

Fiddle: http://jsfiddle.net/2mBdL/

Thanks.

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

It's useful to write a search function in such a way that it returns a negative value indicating the insertion point for the new element if the element is not found. Also, using recursion in a binary search is excessive and unnecessary. And finally, it's a good practice to make the search algorithm generic by supplying a comparator function as a parameter. Below is the implementation.

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

This code with comments and a unit test here.