binary search中不明白的一点问题.

Python/PHP/Perl 开发与设计
回复
drongh
帖子: 1038
注册时间: 2007-01-10 9:32
送出感谢: 4 次
接收感谢: 5 次

binary search中不明白的一点问题.

#1

帖子 drongh » 2013-02-28 12:38

代码: 全选

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
上次由 drongh 在 2013-02-28 14:23,总共编辑 2 次。
头像
枫叶饭团
论坛版主
帖子: 14685
注册时间: 2010-06-16 1:05
系统: Mac OS X
来自: Tencent
送出感谢: 1 次
接收感谢: 132 次
联系:

Re: binary search中不明白的一点问题.

#2

帖子 枫叶饭团 » 2013-02-28 13:16

已经查找过的数当然应该直接去掉啊
头像
cuihao
帖子: 4793
注册时间: 2008-07-24 11:33
来自: 郑州
送出感谢: 1 次
接收感谢: 89 次
联系:

Re: binary search中不明白的一点问题.

#3

帖子 cuihao » 2013-02-28 13:17

必须有一个加一或减一吧。
比如吧,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: ~まだ見ぬ誰かの笑顔のために~
drongh
帖子: 1038
注册时间: 2007-01-10 9:32
送出感谢: 4 次
接收感谢: 5 次

Re: binary search中不明白的一点问题.

#4

帖子 drongh » 2013-02-28 14:22

cuihao 写了:必须有一个加一或减一吧。
比如吧,lb=3,ub=4时,mid是3,如果查找目标在4,而lb不加一,那么lb就永远是3,死循环了。
刚刚调试了一下,对于目标在表中的,可以通过测试.
如果不在表中的,就是死循环,就像楼上说的,lb 永远不会等于 ub了
回复

回到 “Python/Php/Perl”