python 二分搜索练习

Question

我已经看了一段时间了，我看不出我的二分搜索有什么问题。如果我运行它，它会说 'RecursionError: maximum recursion depth exceeded in comparison'。任何人都可以看看下面有什么问题吗？谢谢！

#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 和 return 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())

python 二分搜索练习

python bisection search exercise

python

bisection