Created
August 23, 2013 14:42
-
-
Save markbiek/6320086 to your computer and use it in GitHub Desktop.
Javascript recursive binary search
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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