您好,匿名用户
随意问技术百科期待您的加入

插值查找的问题

0 投票
def interpolation_search(list, key):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (key - list[low]) / (list[high] - list[low]) * (high - low) + low
        if key < list[mid]:
            high = mid - 1
        elif key > list[mid]:
            low = mid + 1
        else:
            return mid
    return -1

最近在学习算法,这是用python写的一个插值查找。
我预先定义了一个list

list = [1, 3, 5, 6, 8, 14, 44, 55, 67, 78]

当我去查询45的时候会出现无限循环

interpolation_search(list, 45)

而当我去查询76的时候会提示ZeroDivisionError

interpolation_search(list, 76)
ZeroDivisionError: integer division or modulo by zero

请大神指点,非常感谢!

用户头像 提问 2012年 12月1日 @ Fiddlesticks 上等兵 (242 威望)
分享到:

1个回答

0 投票

加2行,自己看输出DEBUG。

def interpolation_search(list, key):
    low = 0 
    high = len(list) - 1 
    while low <= high:
        mid = (key - list[low]) / (list[high] - list[low]) * (high - low) + low 
        print "key = %d, mid = %d, list[mid] = %d" % (key, mid, list[mid])
        raw_input()
        if key < list[mid]:
            high = mid - 1 
        elif key > list[mid]:
            low = mid + 1 
        else:
            return mid 
    return -1
用户头像 回复 2012年 12月1日 @ Rammus 上等兵 (334 威望)
提一个问题:

相关问题

0 投票
1 回复 39 阅读
用户头像 提问 2012年 12月1日 @ Hecarim 上等兵 (361 威望)
+1 投票
1 回复 41 阅读
用户头像 提问 2012年 12月1日 @ Sagittarius 上等兵 (289 威望)
0 投票
1 回复 1 阅读
0 投票
1 回复 43 阅读
0 投票
0 回复 19 阅读
用户头像 提问 2013年 9月10日 @ Draven 上等兵 (325 威望)

欢迎来到随意问技术百科, 这是一个面向专业开发者的IT问答网站,提供途径助开发者查找IT技术方案,解决程序bug和网站运维难题等。
温馨提示:本网站禁止用户发布与IT技术无关的、粗浅的、毫无意义的或者违法国家法规的等不合理内容,谢谢支持。

欢迎访问随意问技术百科,为了给您提供更好的服务,请及时反馈您的意见。
...