问题描述:

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?

随机阅读：

- jmail - How to fix remove whitespace from email headers in classic ASP?
- java - What is the difference between ArrayList al = new ArrayList(); and ArrayList al = new ArrayList(0)?
- 中国2010上海世博会的主题是“城市，让生活更美好”．（1）上海世博园上空飘浮着“鲸鱼”状巨大的系留气球，全天候为世博会安全保障、电视转播提供服务．为了安全，气球内充
- 根据表中数据，正确的分析是动物名称心脏占体重比例%每分钟心跳次数蛙0.5722人0.4272鸽1.72135--244A.鸽的心脏占体重的百分比比其他两种动物高，因此

**推荐内容**-

**热点内容**