问题描述:

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

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 likelinear search.

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:

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

.**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:

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

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

.**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