python二分搜索练习

Question

我已经看了很长一段时间了，我不知道我的二分法搜索有什么问题。如果我运行它，它会说'RecursionError:相对地超过最大递归深度‘。有人能看看下面是怎么回事吗？谢谢!

#Write a function called in_bisect 
#that takes a sorted list and a target value 
#and returns the index
#of the value in the list if it’s there

def in_bisect(t, word):

    if len(t) == 0:
        return False

    middle = len(t) // 2

    if t[middle] == word:
        return middle

    elif t[middle] > word:
        return in_bisect(t[:middle], word)
    else:
        return in_bisect(t[middle:], word)


if __name__ == "__main__":
    fruits = ['apple', 'banana', 'kiwi', 'peach', 'watermelon']

    in_bisect(fruits, 'banana')
    in_bisect(fruits, 'ewf')        

Answer 1

想象一下，当列表长度为1时会发生什么，那么中间的值是0。如果现在最后的else情况是实际的情况，递归将再次得到相同的列表(大小)，结果是相同的.无限递归

解决方案:在middle中添加一个，此时您已经知道middle本身不再是候选人了：

else:
    return in_bisect(t[middle+1:], word)

Answer 2

我将在这里使用循环而不是递归，因为Python不能将尾部递归转换为循环，而且递归深度限制很低。

我还会检查word在t中是什么，否则返回False。

def in_bisect(t, word):
    def iterator(start, end):
        # loop will terminate when exactly start = end - 1
        while start < end - 1:
            middle = (start + end) // 2
            if t[middle] == word:
                return middle
            elif t[middle] > word:
                end = middle
            else:
                start = middle + 1
        # here we need to check wheither the last element in the list is the one we search for
        return start if t[start] == word else False

    # if len(t) is zero, our inner function would raise IndexError so we check it explicitly
    if len(t) == 0:
        return False
    return iterator(0, len(t))

Answer 3

fruits = ['apple', 'banana', 'kiwi', 'peach', 'watermelon','dog','cat']

def in_bisect(t, word):
    # cheks if the word is in the list 
    if word not in t:
        return False 
    if len(t)==0:
        return False
    low=0
    high=len(fruits)
    #loop will when the value is found 
    while True:
        mid=(low + high)//2

        if t[mid]==word:

            return mid,t[mid]
        if word in t[:mid]  :
            high=mid
        else:
            low=mid
def test():
    print(in_bisect(fruits, 'apple'))
    print(in_bisect(fruits, 'banana'))
    print(in_bisect(fruits, 'kiwi'))
    print(in_bisect(fruits, 'dog'))
    print(in_bisect(fruits, 'ewf')   )
    print(in_bisect(fruits, 'banana'))
    return 'Test completed sucssfuly'
print (test())