How to keep Javascript array sorted, without sorting it

Question

I have a Node.js application where I have to very often do following things: - check if particular array already contains certain element - if element does exist, update it - if element do not exist, push it to the array and then sort it using underscore _.sortBy

For checking if the element already exists in the array, I use this binary search function: http://oli.me.uk/2013/06/08/searching-javascript-arrays-with-a-binary-search/

In this way, when the size of the array grows, the sorting becomes slower and slower. I assume that the array size might grow to max 20 000 items per user. And eventually there will be thousands of users. The array is sorted by a key, which is quite a short string. It can be converted into integer if needed.

So, I would require a better way to keep the array sorted, in stead of sorting it every time new element is pushed onto it.

So, my question is, how should/could I edit the binary search algorithm I use, to enable me to get the array index where the new element should be placed, if it doesn't already exist in the array? Or what other possibilities there would be to achieve this. Of course, I could use some kind of loop that would start from the beginning and go through the array until it would find the place for the new element.

All the data is stored in MongoDB.

In other words, I would like to keep the array sorted without sorting it every time a new element is pushed.

Answer 1

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

Answer 2

If your array is already sorted and you want to insert an element, to keep it sorted you need to insert it at a specific place in the array. Luckily arrays have a method that can do that: Array.prototype.splice

So, once you get the index you need to insert at (you should get by a simple modification to your binary search), you can do:

myArr.splice(myIndex,0,myObj);
// myArr your sorted array
// myIndex the index of the first item larger than the one you want to insert
// myObj the item you want to insert

EDIT: The author of your binary search code has the same idea:

So if you wanted to insert a value and wanted to know where you should put it, you could run the function and use the returned number to splice the value into the array. Source