Skip to main content
added 794 characters in body
Source Link
Rafael
  • 171
  • 4

Binding it to the array prototype has its benefits though. Consider....

//https://github.com/MrOutput/learning/blob/master/js/binary_search.js
Array.prototype.bsearch = function (fn) {
    var low, mid, high;
    low ^= low;
    high = this.length - 1;
    while (low <= high) {
        mid = (low + high) >> 1;
        var cmp = fn(this[mid]);
        if (cmp < 0) {
            high = mid - 1;
        } else if (cmp > 0) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
};

var FIND = 100;
var arr = [ 9, 8, 10, 100, 60, 1 ];
var i = arr .sort((a, b) => a - b).bsearch(n => FIND - n);

console.log('FOUND AT', i);

Binding it to the array prototype has its benefits though. Consider....

//https://github.com/MrOutput/learning/blob/master/js/binary_search.js
Array.prototype.bsearch = function (fn) {
    var low, mid, high;
    low ^= low;
    high = this.length - 1;
    while (low <= high) {
        mid = (low + high) >> 1;
        var cmp = fn(this[mid]);
        if (cmp < 0) {
            high = mid - 1;
        } else if (cmp > 0) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
};

var FIND = 100;
var arr = [ 9, 8, 10, 100, 60, 1 ];
var i = arr .sort((a, b) => a - b).bsearch(n => FIND - n);

console.log('FOUND AT', i);
Source Link
Rafael
  • 171
  • 4

arrays in js already have a sort method, all it needs is a compare function. I made a similar api for a general binary search. It takes an array as its first arg and the compare func as the second. The binary search function could be bound to the Array prototype too. But people complain too much about extending the native prototypes, so we'll just pass the array in.

The style here is consistent. The indentation is the same and the variable names are short yet descriptive enough. Each function does 1 thing and nothing more.

var FIND = 100;
var arr = [ 9, 8, 10, 100, 60, 1 ];

var sorted = arr.sort((a, b) => a - b);
console.log(sorted);

var i = binary_search(sorted, n => FIND - n);
console.log('FOUND AT', i);

//https://github.com/MrOutput/learning/blob/master/js/binary_search.js
function binary_search(array, fn) {
    var low, mid, high;
    low ^= low;
    high = array.length - 1;
    while (low <= high) {
        mid = (low + high) >> 1;
        var cmp = fn(array[mid]);
        if (cmp < 0) {
            high = mid - 1;
        } else if (cmp > 0) {
            low = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}