如何向按对象数值属性排序的对象数组中插入元素（含重复值场景）

在标准线性数组的存储场景下，你目前使用的「二分查找定位最后一个匹配索引后插入」的方案已经是通用最优解，不存在效率更高的通用解决方案。

核心原因分析 #

• 查找阶段的时间复杂度已经达到理论最优：针对允许重复值的升序数组，查找指定值最后一次出现的位置，二分查找的时间复杂度为O(log n)，不存在比对数复杂度更低的通用查找方案。
• 插入阶段的耗时是线性数组的结构固有约束：在数组中间位置插入元素时，必须移动插入位置之后的所有元素，这一步的时间复杂度固定为O(n)，和查找方式无关，无法进一步优化。

特定场景下的优化方案 #

如果你的业务场景符合以下特征，可以改用更适配的存储结构来提升插入效率：

1. 插入操作远多于随机查询操作
   可将存储结构从数组替换为双向链表，查找定位到最后一个匹配项后，插入操作的时间复杂度可降低到O(1)，但对应随机访问指定位置元素的时间复杂度会上升到O(n)，需要根据业务访问特征权衡。
2. 高频插入、低频全量有序遍历
   可改用分组存储结构：以Map<number, Array<object>>存储数据，键为NumericOrder的值，值为对应NumericOrder的所有对象数组。插入时直接取对应NumericOrder的数组执行push操作即可，时间复杂度为O(1)；需要输出全量有序数组时，再对键排序后展开所有分组数组即可。

现有方案的最优实现示例（JavaScript） #

// 查找升序数组中NumericOrder等于目标值的最后一个元素索引
function findLastMatchIndex(sortedArr, targetNum) {
  let left = 0;
  let right = sortedArr.length - 1;
  let lastMatchIndex = -1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const currentVal = sortedArr[mid].NumericOrder;
    if (currentVal === targetNum) {
      lastMatchIndex = mid;
      left = mid + 1; // 继续向右查找是否有相同值的元素
    } else if (currentVal < targetNum) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return lastMatchIndex;
}

// 插入操作
const sortedArr = [
  {NumericOrder : 1, Name:"Test1"},
  {NumericOrder: 1, Name:"Test2"},
  {NumericOrder:2,Name: "Test 3"},
  {NumericOrder : 3, Name:"Test4"},
  {NumericOrder : 4, Name:"Test5"},
  {NumericOrder:5,Name: "Test 6"},
];
const newItem = {NumericOrder: 1 , Name : "Test7"};
const insertPosition = findLastMatchIndex(sortedArr, 1) + 1;
sortedArr.splice(insertPosition, 0, newItem);

内容的提问来源于stack exchange，提问作者Faisal