当前位置: 动力学知识库 > 问答 > 编程问答 >

arrays - Complexity for Binary Search (Insertion) for an ordered list

问题描述:

I understand that binary search cannot be done for an unordered array.

I also understand that the complexity of a binary search in an ordered array is O(log(n)).

Can I ask

  1. what is the complexity for binary search(insertion) for an

    ordered array? I saw from a textbook, it stated that the complexity

    is O(n). Why isn't it O(1) since, it can insert directly, just like

    linear search.

  2. Since binary search can't be done in unordered list, why is it

    possible to do insertion, with a complexity of O(N)?

网友答案:

insertion into list complexity depends on used data structure:

  1. linear array

    In this case you need to move all the items from index of inserting by one item so you make room for new inserted item. This is complexity O(n).

  2. linked list

    In this case you just changing the pointers of prev/next item so this is O(1)

Now for the ordered list if you want to use binary search (as you noticed) you can use only array. The bin-search insertion of item a0 into ordered array a[n] means this:

  1. find where to place a0

    This is the bin search part so for example find index ix such that:

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

    This can be done by bin search in O(log(n))

  2. insert the item

    so you need first to move all the items i>=ix by one to make place and then place the item:

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

    As you can see this is O(n).

  3. put all together

    so O(n+log(n)) = O(n) that is why.

BTW. search on not strictly ordered dataset is possible (although it is not called binary search anymore) see

  • How approximation search works
分享给朋友:
您可能感兴趣的文章:
随机阅读: