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

Question

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

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

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

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

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

所有数据都存储在 MongoDB 中。

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

Answer 1

很容易修改此 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}

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

所以，现在插入一个新元素看起来像这样:

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

现在您可以将 binaryFind 添加到 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);
}