Skip to content

Instantly share code, notes, and snippets.

@markbiek
Created August 23, 2013 14:42
Show Gist options
  • Save markbiek/6320086 to your computer and use it in GitHub Desktop.
Save markbiek/6320086 to your computer and use it in GitHub Desktop.
Javascript recursive binary search
Object.prototype.bsearch = function(i, min, max) {
//console.log('Finding ' + i + ' out of ' + this.length + ' items');
if(max < min) {
return 0;
}else {
var mid = Math.floor((min + max) / 2);
//console.log('Midpoint of ' + min + '->' + max + ' is ' + mid);
if(this[mid] > i) {
//search the lower half
return this.bsearch(i, min, mid-1);
}else if(this[mid] < i) {
//search the upper half
return this.bsearch(i, mid+1, max);
}else {
//found
return mid;
}
}
};
var a = [];
for(i=0; i<100; i++) {
a[i] = i+1;
}
console.log(a);
for(i=1; i<=20; i++) {
console.log('Found ' + i + ' at index ' + a.bsearch(i, 1, a.length));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment