It's easy to modify this binaryIndexOf
function to return an index of the next element when no matches found:
function binaryFind(searchElement) {
'use strict';
var minIndex = 0;
var maxIndex = this.length - 1;
var currentIndex;
var currentElement;
while (minIndex <= maxIndex) {
currentIndex = (minIndex + maxIndex) / 2 | 0; // Binary hack. Faster than Math.floor
currentElement = this[currentIndex];
if (currentElement < searchElement) {
minIndex = currentIndex + 1;
}
else if (currentElement > searchElement) {
maxIndex = currentIndex - 1;
}
else {
return { // Modification
found: true,
index: currentIndex
};
}
}
return { // Modification
found: false,
index: currentElement < searchElement ? currentIndex + 1 : currentIndex
};
}
So, now it returns objects like:
{found: false, index: 4}
where index
is an index of the found element, or the next one.
So, now insertion of a new element will look like:
var res = binaryFind.call(arr, element);
if (!res.found) arr.splice(res.index, 0, element);
Now you may add binaryFind
to Array.prototype
along with some helper for adding new elements:
Array.prototype.binaryFind = binaryFind;
Array.prototype.addSorted = function(element) {
var res = this.binaryFind(element);
if (!res.found) this.splice(res.index, 0, element);
}