插值查找的问题

Question

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

请大神指点，非常感谢！

Answer 1

加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