arrays - 有序列表的二进制搜索(插入)的复杂性

Question

我知道无法对无序数组进行二分查找。我还了解到，在有序数组中进行二分查找的复杂度为 O(log(n))。

可以问一下吗

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

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

Answer 1

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

1. 线性阵列

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

2. 链表

   在这种情况下，您只需更改上一个/下一个项目的指针，所以这是 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 search 来完成

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) 这就是原因。

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

• How approximation search works