Created
October 11, 2019 01:54
-
-
Save 1fabiopereira/b1eefc6a567bc2d5f2b7420044c3df00 to your computer and use it in GitHub Desktop.
This file contains 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
/* | |
target: the object to search for in the array | |
comparator: (optional) a method for comparing the target object type | |
return value: index of a matching item in the array if one exists, otherwise the bitwise complement of the index where the item belongs | |
*/ | |
Array.prototype.binarySearch = function (target, comparator) { | |
var l = 0, | |
h = this.length - 1, | |
m, comparison; | |
comparator = comparator || function (a, b) { | |
return (a < b ? -1 : (a > b ? 1 : 0)); /* default comparison method if one was not provided */ | |
}; | |
while (l <= h) { | |
m = (l + h) >>> 1; /* equivalent to Math.floor((l + h) / 2) but faster */ | |
comparison = comparator(this[m], target); | |
if (comparison < 0) { | |
l = m + 1; | |
} else if (comparison > 0) { | |
h = m - 1; | |
} else { | |
return m; | |
} | |
} | |
return~l; | |
}; | |
/* | |
target: the object to insert into the array | |
duplicate: (optional) whether to insert the object into the array even if a matching object already exists in the array (false by default) | |
comparator: (optional) a method for comparing the target object type | |
return value: the index where the object was inserted into the array, or the index of a matching object in the array if a match was found and the duplicate parameter was false | |
*/ | |
Array.prototype.binaryInsert = function (target, duplicate, comparator) { | |
var i = this.binarySearch(target, comparator); | |
if (i >= 0) { /* if the binarySearch return value was zero or positive, a matching object was found */ | |
if (!duplicate) { | |
return i; | |
} | |
} else { /* if the return value was negative, the bitwise complement of the return value is the correct index for this object */ | |
i = ~i; | |
} | |
this.splice(i, 0, target); | |
return i; | |
}; | |
const arr = []; | |
arr.binaryInsert("Zebra"); | |
arr.binaryInsert("Aardvark"); | |
arr.binaryInsert("Mongoose"); | |
console.log(arr); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment