注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

小木舟的博客

笔墨生活随想,记录似水年华。

 
 
 

日志

 
 

一个优秀的二分搜索程序  

2010-04-25 14:37:16|  分类: 编程学习 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

最近时常会翻阅《编程珠玑(第二版)》这本书,一次偶然的机会看到了一个效率很高的很优秀的二分搜索程序,忍不住在这里要和大家分享下。废话少说,现在进入主题。

一般的二分搜索算法如下所示:

l = 0; u = n-1

loop

    /* invariant: if t is present, it is in x[l:u]*/

    if l > u

        p = -1;break

    m = ( l + u)/2

    case

    x[m] < t: l = m+1

    x[m] == t: p = m; break

x[m] > t: u = m-1

    在上面所示的这段代码当中,针对一般的t没有重复出现且可以返回t出现的任意位置的情况是没问题的。但是若是要确定整数数组x[0..n-1]t第一次出现的位置,且t在数组中是多次出现的话,上述代码则可能会返回其中的任意一个位置。上面我们将要给出的优化的代码的主循环与上面的程序类似;我们仍将使用下标lu指示数组中包含t的部分,但不变式关系为x[l]<t<=x[u]l<u。此外,我们假设n>=0,x[-1]<t以及x[n]>=t(但是程序并不访问者两个假想的元素)。现在的二分搜索代码如下所示:

l = -1; u = n

while l+1 != u

    /* invariant: x[l] < t && x[u] >= t && l < u */

    m = ( l + u)/2

    if x[m] < t

        l = m

    else

        u = m

    /* assert l+1 = u && x[l] < t && x[u] >= t*/

    p = u

    if p >= n || x[p] != t

        p = -1

    在上面所示代码中,循环重复时,由if语句来保持该不等式的正确性。当循环结束时,我们知道如果t存在于数组中,那么t的第一次出现在位置u。最后两个语句对p赋值:如果tx中,那么将p置为t第一次出现的下标;如果t不在数组中,则将p置为-1

    虽然第二个程序所解决的问题要比第一个程序所解决的问题更难,但却可能更高效:在每次循环迭代中,他只对tx中的元素做一次比较,而原先的程序有时必须比较两次。当数据量比较大的时候,第二个程序的效率就比较明显了。一般而言,第二个程序的运行速度通常是第一个程序的23倍。

    好的程序设计让人回味无穷,就如同一杯好茶,喝完之后依旧让人荡气回肠。

  评论这张
 
阅读(310)| 评论(0)
推荐

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017