I have to create a binary search algorithm through recursion.
Code:
theList = ['boa','cat','dog','eel','fish','gerbil','hamster','pig','tarantula']
def bSearch(lst, key, index, leng):
print("//////////////////////////")
index = int(index)
leng = int(leng)
print("Comparing ", lst[index], " and ", key)
print("Index ", index, " Length " , leng)
if lst[index] == key:
return index
if index == 0 or index == 8:
return -1
print("Is lst[index] > key?: ", lst[index] > key)
if (lst[index] > key):
print("Decrease Index " , leng/2, " leng " , leng/2)
return bSearch(lst, key, index - leng/2, leng - leng/2)
print("Increase index ", leng/2, " leng " , leng/2)
return bSearch(lst, key, index + leng/2, leng - leng/2)
It can find every key except for tarantula. If I search for it I is an infinite loop?
I can figure out where my logic fails but not how to solve it...
At the end I keep adding 0 to both of the parameters.