I have been looking at it for a while and I cannot see what is wrong with my bisection search. If I run it, it says 'RecursionError: maximum recursion depth exceeded in comparison'. Could anybody have a look and see what is wrong below? Thank you!
#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')
Imagine what happens when the list length is 1. Then the middle will be 0. If now the final else case is the actual one, the recursion will get the same list (size) again, with the same result... infinite recursion.
Solution: add one to middle as at that moment you already know that middle itself is no longer a candidate:
else:
return in_bisect(t[middle+1:], word)