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))`.

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)`.

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

Top