如何保持Javascript数组排序，而不对其进行排序

我有一个 Node.js 应用程序，我必须经常执行以下操作： - 检查特定数组是否已包含特定元素 - 如果元素确实存在，则更新它 - 如果元素不存在，则将其推入数组，然后使用下划线_.sortBy对其进行排序

为了检查该元素是否已存在于数组中，我使用这个二分搜索函数：http://oli.me.uk/2013/06/08/searching-javascript-arrays-with-a-binary-search/ http://oli.me.uk/2013/06/08/searching-javascript-arrays-with-a-binary-search/

这样，当数组的大小变大时，排序就会变得越来越慢。 我假设数组大小可能会增长到每个用户最多 20 000 个项目。最终将有数千名用户。该数组按键排序，该键是一个很短的字符串。如果需要，可以将其转换为整数。

所以，我需要一种更好的方法来保持数组排序， 而不是每次将新元素推入其中时对其进行排序。

所以，我的问题是，我应该/如何编辑我使用的二分搜索算法，以使我能够 如果数组中尚不存在，获取应放置新元素的数组索引？ 或者还有哪些其他可能性可以实现这一目标。当然，我可以使用某种从头开始并遍历数组的循环，直到找到新元素的位置。

所有数据都存储在 MongoDB 中。

换句话说，我希望保持数组排序，而不是每次推送新元素时都对其进行排序。

修改这个很容易binaryIndexOf未找到匹配项时返回下一个元素的索引的函数：

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

所以，现在它返回如下对象：

{found: false, index: 4}

where index是找到的元素或下一个元素的索引。

因此，现在插入一个新元素将如下所示：

var res = binaryFind.call(arr, element);
if (!res.found) arr.splice(res.index, 0, element);

现在您可以添加binaryFind to Array.prototype以及一些用于添加新元素的助手：

Array.prototype.binaryFind = binaryFind;

Array.prototype.addSorted = function(element) {
  var res = this.binaryFind(element);
  if (!res.found) this.splice(res.index, 0, element);
}