问题描述:

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

您可能感兴趣的文章：

- ios - I don't know how to code my query sentence on Core Data with NSPredicate
- pdfminer - Automate dekstop screening with Python
- Cygwin and WinPcap 4.1.3 timestamp - microsecond issue - header->ts.tv_usec not correct - C program
- sql - select multiple cells in a table with the same value in c#
- geometry - Transform a triangle on a plane
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**-
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- WCF in Winforms app - is it always single-threaded?
- git svn - git svn fetch does not fetch a Subversion commit message modified after initial clone
- java me - Why I am getting the bad length exception when I am running this application?
- java - How to get string.format to complain at compile time
- ruby on rails - Trigger observer of parent class on change
- python - Issue with URL pattern in Django with webmonkey tutorial