BinarySearch

by antelopelovefan

JavaScript

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