{技术}{讨论}编程猪鸡上关于二分的问题

[27149]

书上有个题说到：

二分查找经常会被误用在未排好序的数组上。在查找之前完全检查是否排好序耗费n-1次比较。如何能在函数中加入部分检查以明显降低消耗？

后面的提示是Theta（lgn）和Theta（1）两种方法。

感觉很奇怪，不知有何好方法呢？

[sagasw]

代码有限制？不可以加个bool做标记么？

2009/9/21 27149 <bupt....@gmail.com>

[27149]

问题的意思应该是需要做排序检查吧......

On 9月22日, 上午9时06分, sagasw <sag...@gmail.com> wrote:
> 代码有限制？不可以加个bool做标记么？
>
> 2009/9/21 27149 <bupt.sun...@gmail.com>

>
>
>
> > 书上有个题说到：
>
> > 二分查找经常会被误用在未排好序的数组上。在查找之前完全检查是否排好序耗费n-1次比较。如何能在函数中加入部分检查以明显降低消耗？
>
> > 后面的提示是Theta（lgn）和Theta（1）两种方法。
>

> > 感觉很奇怪，不知有何好方法呢？- 隐藏被引用文字 -
>
> - 显示引用的文字 -

[Wu Yin]

有序检查不存在最差情况低于n-1次的算法吧

2009/9/22 27149 <bupt....@gmail.com>

--
滚滚长江东逝水，浪花淘尽英雄。
是非成败转头空。
青山依旧在，几度夕阳红。
白发渔樵江渚上，惯看秋月春风。
一壶浊酒喜相逢。
古今多少事，都付笑谈中。