如何在排序的索引位置将元素推入数组？

Question

假设我已经有一个包含这些文章的数组，按价格从低到高排序：

[
  { title: "Article 3", price: 1.49 },
  { title: "Article 1", price: 3.00 },
  { title: "Article 4", price: 5.99 },
  { title: "Article 2", price: 19.99 }
]

基本上我想在正确的位置（按价格）将另一篇文章推入数组。我怎么能这样做？

我正在推送的新文章可能具有以下属性：

{ title: "Article 5", price: 12.00 }

我期待这篇文章出现在索引 3（在文章 4 和 2 之间）。

更新（解决方案）

我使用@klutt 的答案和二进制搜索算法创建了一个原型方法：

Array.prototype.pushSorted = function(el, compareFn) {
  this.splice((function(arr) {
    var m = 0;
    var n = arr.length - 1;

    while(m <= n) {
      var k = (n + m) >> 1;
      var cmp = compareFn(el, arr[k]);

      if(cmp > 0) m = k + 1;
        else if(cmp < 0) n = k - 1;
        else return k;
    }

    return -m - 1;
  })(this), 0, el);

  return this.length;
};

const sortByPrice = (a, b) => a.price > b.price;
theArray.pushSorted({ title: "Article 5", price: 12.00 }, sortByPrice);

Answer 1

如果它是一个很长的列表，您不想每次都对列表​​进行排序。使用浮点数排序最多是 O(n*log n)。如果您进行线性搜索，您将得到 O(n)。

function search(a, v) {
    if(a[0]['price'] > v['price']) {
        return 0;
    }
    var i=1;
    while (i<a.length && !(a[i]['price'] > v['price'] && a[i-1]['price'] <= v['price'])) {
        i=i+1;
        }
    return i;
}

myArray.splice(search(myArray, newItem), 0, newItem)

但是，如果列表很长，最好进行二分搜索而不是线性搜索。这将把它降低到 O(log n)。二分查找非常简单。你从中间开始。如果元素大于您要搜索的元素，则将相同的算法应用于列表的上半部分，否则应用于下半部分。在网上很容易找到二进制搜索的代码示例。

下面是一个例子：

function binarySearch(ar, el, compare_fn) {
    if (el.price < ar[0].price)
        return 0;
    if (el.price > ar[ar.length-1].price)
        return ar.length;
    var m = 0;
    var n = ar.length - 1;
    while (m <= n) {
        var k = (n + m) >> 1;
        var cmp = compare_fn(el, ar[k]);
        if (cmp > 0) {
            m = k + 1;
        } else if(cmp < 0) {
            n = k - 1;
        } else {
            return k;
        }
    }
    return -m - 1;
}

function comp(a, b) {
    return a['price']>b['price']
}

myArray.splice(binarySearch(myArray, element, comp), 0, element)

（从此处窃取的Javascript 二进制搜索）

但是要把它包起来。添加元素然后排序通常是一个坏主意。最好的情况是没关系，但既然你知道列表是排序的，为什么不至少做一个线性搜索呢？

如果列表很小，这无关紧要，但如果列表有数百万个元素，则差异将非常明显。

编辑：

我做了一个快速而原始的基准测试。

            10,000   100,000  1000,000   10,000,000  
Sort            80       900     13000          N/A
Linear           2         2        25         5000
Binary           2         2         5           21

我测量了在四种不同尺寸上运行三种算法所需的时间。我不想等待排序以一千万个元素结束。因此不适用。时间以毫秒为单位。请注意，基准测试非常原始，但它提供了有关大小增长时它会产生多大影响的想法。