如何在排序的JavaScript数组中找到插入索引？

只要排序数组能够保持其排序顺序，它就非常有用。不幸的是，将一个新元素插入到排序数组中并不像将其推到数组的末尾那样简单。相反，它需要找到正确的索引来插入。

[!NOTE]

本文中呈现的代码片段宽松地检查数组是否按升序或降序排序。如果你想更严格一些或者有相应的检查，请修改代码以反映这一点。

排序数组中的插入索引

要找到排序数组中元素的最低插入索引，可以使用Array.prototype.findIndex()来找到应该插入元素的适当索引。

const insertionIndex = (arr, n) => {
  const isDescending = arr[0] > arr[arr.length - 1];
  const index = arr.findIndex(el => (isDescending ? n >= el : n <= el));
  return index === -1 ? arr.length : index;
};

insertionIndex([5, 3, 2, 1], 4); // 1
insertionIndex([30, 50], 40); // 1

相反，要找到排序数组中元素的最高插入索引，可以使用Array.prototype.findLastIndex()来找到应该插入元素的适当索引。

const lastInsertionIndex = (arr, n) => {
  const isDescending = arr[0] > arr[arr.length - 1];
  const index = arr.findLastIndex(el => (isDescending ? n <= el : n >= el));
  return index === -1 ? arr.length : index;
};

lastInsertionIndex([10, 20, 30, 30, 40], 30); // 3

使用比较函数确定插入索引

对于更复杂的数据，您可能需要一个比较函数来确定插入索引。例如，如果您有一个对象数组，您可能希望根据每个对象的特定属性来找到插入索引。

该技术与上面的方法相同，只是在将给定的比较函数应用于数组的每个元素之前进行比较。

比较函数期望两个要比较的元素，并且如果它们相等，则返回0，如果第一个元素在第二个元素之前，则返回负数，如果第一个元素在第二个元素之后，则返回正数。在降序的情况下，元素的顺序应该被颠倒。

const insertionIndexBy = (arr, n, comparatorFn) => {
  const index = arr.findIndex(el => comparatorFn(n, el) < 0);
  return index === -1 ? arr.length : index;
};

insertionIndexBy([{ x: 4 }, { x: 6 }], { x: 5 }, (a, b) => a.x - b.x); // 1
insertionIndexBy([{ x: 6 }, { x: 4 }], { x: 5 }, (a, b) => b.x - a.x); // 1