4m1r - 1 year ago 105
Javascript Question

# Binary Search in 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?

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);
``````

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

See a working fiddle

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download