如何在排序数组中插入元素，使数组保持排序状态

Question

在 c++ 中，std::set按排序顺序存储其元素可以在 O（log n） 时间内插入元素。但是我知道的所有方法都需要线性时间：

在

数组末尾插入元素并将其与前一个元素交换，直到前一个元素小于它需要线性时间。

在数组上使用二叉搜索并查找要插入的元素的位置：需要 O（log n） 时间，但在最坏的情况下将元素插入给定位置需要 O（n） 时间。

如果我们使用排序数组作为堆，我们可以在 O（log n） 时间内插入一个元素，但即使数组在此之后仍然是堆，也不能保证它保持排序状态。

我需要一种方法在 O（log n） 时间内将元素插入排序数组中，我知道这是可能的，因为std::set可以做到，但我不知道怎么做。

Answer 1

解决方案是使用不同的数据结构。 例如，std::set已经使用红黑树实现。

通常，不能使用纯数组执行此操作。