有序列表的二进制搜索（插入）的复杂性

Question

我知道无法对无序数组进行二分查找。 我也明白在有序数组中进行二分查找的复杂度是 O(log(n)).

可以问一下吗

1. 二进制搜索（插入）的复杂度是多少 有序数组？我从教科书上看到，它说复杂性 是 O(n)。为什么不是 O(1) 因为，它可以直接插入，就像 线性搜索。

2. 既然无序列表不能进行二分查找，为什么 可以插入，复杂度为 O(N)?

Answer 1

插入列表的复杂性取决于使用的数据结构：

1. 线性数组

   在这种情况下，您需要将所有项目从插入索引中移动一个项目，以便为新插入的项目腾出空间。这是复杂度 O(n).

2. 链表

   在这种情况下，您只需更改 prev/next 项目的指针，因此这是 O(1)

现在对于有序列表，如果你想使用二进制搜索（正如你注意到的那样），你只能使用数组。项目 a0 到有序数组 a[n] 的 bin-search 插入意味着：

1. 查找放置位置a0

   这是 bin 搜索部分，例如找到索引 ix 这样：

   a[ix-1]<=a0 AND a[ix]>a0 // for ascending order
   

   这可以通过 O(log(n))

中的 bin 搜索来完成

2. 插入项目

   所以你需要先将所有物品 i>=ix 移动一个位置，然后放置物品：

   for (int i=n;i>ix;i--) a[i]=a[i-1]; a[ix]=a0; n++;
   

   如您所见，这是 O(n)。

3. 放在一起

   所以O(n+log(n)) = O(n)这就是为什么。

顺便说一句。可以搜索非严格排序的数据集（虽然它不再称为二进制搜索）参见