当前时区为 UTC + 8 小时



发表新帖 回复这个主题  [ 4 篇帖子 ] 
作者 内容
1 楼 
 文章标题 : binary search中不明白的一点问题.
帖子发表于 : 2013-02-28 12:38 

注册: 2007-01-10 9:32
帖子: 1038
送出感谢: 4
接收感谢: 5
代码:
def search_binary(xs, target):
    """ Find and return the index of key in sequence xs """
    lb = 0
    ub = len(xs)
    while True:
        if lb == ub:   # If region of interest (ROI) becomes empty
            return -1

        # Next probe should be in the middle of the ROI
        mid_index = (lb + ub) // 2

        # Fetch the item at that position
        item_at_mid = xs[mid_index]

        # print("ROI[{0}:{1}](size={2}), probed='{3}', target='{4}'"
        #       .format(lb, ub, ub-lb, item_at_mid, target))

        # How does the probed item compare to the target?
        if item_at_mid == target:
            return mid_index      # Found it!
        if item_at_mid < target:
            lb = mid_index + 1     # Use upper half of ROI next time
        else:
            ub = mid_index        # Use lower half of ROI next time


_________________
ubuntu技巧 http://wiki.ubuntu.org.cn/index.php?tit ... 6.E5.8C.BA


最后由 drongh 编辑于 2013-02-28 14:23,总共编辑了 2 次

页首
 用户资料  
 
2 楼 
 文章标题 : Re: binary search中不明白的一点问题.
帖子发表于 : 2013-02-28 13:16 
头像

注册: 2010-06-16 1:05
帖子: 14668
地址: Tencent
系统: Mac OS X
送出感谢: 1
接收感谢: 153
已经查找过的数当然应该直接去掉啊


_________________
twitter求fo:http://twitter.com/maplebeats
博客求踩:http://maplebeats.com


页首
 用户资料  
 
3 楼 
 文章标题 : Re: binary search中不明白的一点问题.
帖子发表于 : 2013-02-28 13:17 
头像

注册: 2008-07-24 11:33
帖子: 4793
地址: 郑州
送出感谢: 4
接收感谢: 92
必须有一个加一或减一吧。
比如吧,lb=3,ub=4时,mid是3,如果查找目标在4,而lb不加一,那么lb就永远是3,死循环了。


_________________
求人不如求它仨: 天蓝的Wiki 屎黄的Wiki 绿
Site: CUIHAO.TK    Twitter: @cuihaoleo
Machine: Athlon64 X2 5200+ / 2x2GB DDR2-800 / GeForce GTS 450
AD: ~まだ見ぬ誰かの笑顔のために~


页首
 用户资料  
 
4 楼 
 文章标题 : Re: binary search中不明白的一点问题.
帖子发表于 : 2013-02-28 14:22 

注册: 2007-01-10 9:32
帖子: 1038
送出感谢: 4
接收感谢: 5
cuihao 写道:
必须有一个加一或减一吧。
比如吧,lb=3,ub=4时,mid是3,如果查找目标在4,而lb不加一,那么lb就永远是3,死循环了。


刚刚调试了一下,对于目标在表中的,可以通过测试.
如果不在表中的,就是死循环,就像楼上说的,lb 永远不会等于 ub了


_________________
ubuntu技巧 http://wiki.ubuntu.org.cn/index.php?tit ... 6.E5.8C.BA


页首
 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 4 篇帖子 ] 

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:没有注册用户 和 3 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
本站点为公益性站点,用于推广开源自由软件,由 DiaHosting VPSBudgetVM VPS 提供服务。
我们认为:软件应可免费取得,软件工具在各种语言环境下皆可使用,且不会有任何功能上的差异;
人们应有定制和修改软件的自由,且方式不受限制,只要他们自认为合适。

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
简体中文语系由 王笑宇 翻译