如何在有序数组中插入元素，使数组保持有序？

Question

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

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

在数组上使用二进制搜索并找到要插入的元素的位置:需要O(log )时间，但在最坏的情况下，将元素插入到给定位置需要O(n)时间。

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

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

Answer 1

解决方案是使用不同的数据结构。例如，已经使用red-black-tree实现了std::set。

通常，您不能使用普通数组做到这一点。