HiDanny HiDanny - 1 month ago 11
Python Question

What is wrong with my Recursive Binary-Search program?

I can't seem to figure out why my code keeps on returning N instead of R. I have tested what the letter would be before going to the return statement and as you can see in the image of the output, it should be R. Yet, it continues to return N as shown in the picture and I don't know why it would do that... I have tried hand-tracing the process and I still end up with R. I have included some notes within the code for you to see and understand my thoughts. I have also included a picture of the output at the bottom.

Input: ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']

def binSearch(lst, what):
position = ""
original_lst = lst[:]
if (position == what): # Doesn't do anything since no recursive is made when position is equal to R.
return original_lst.index("%s" %position)
else:
midpoint = (len(lst))//2
position = lst[midpoint]
print("Looking at", position)
if position > what:
lst = lst[:midpoint]
binSearch(lst, what)
elif position < what:
lst = lst[midpoint:]
binSearch(lst, what)
elif position == what: # Removable. Just Testing and seeing what position it results as.
print("Position it ends up in:", position) # when I replace this later, I probably should use a binSearch(). I think?
else:
return -1 # this is for if the letter not found.
return position # Why does it return N... instead of R? This originally was suppose to find the index of the letter on the list. I adjusted it to see what letter the program was searching for instead. It still results in the same problem if I change it to look for the index of letter instead as it looks for **N** instead of **R**
# just to clarify, I was aiming to use return original_lst.index("%s" %position) to find the index of the letter. I just changed it to see what letter its returning instead.



lst = []
while True:
val = input()
if val == "exit":
break
lst.append(val)

print(lst)
lst.sort()
print(lst)

what = input("Enter element to search for:")
print(what)
where = binSearch(lst, what)
if where != -1:
print("Found at position", where)
else:
print("Not found")


Picture of Output

Edit: This program was originally suppose to find the value of the letter. Position was suppose to be the letter and I would just return.index it at the end. However to make it more readable and easier to understand, I changed the return statement at the end. It still ends up with the same results of where it reutrns N instead of R.

Answer

The first time you call the algorithm, N is in the middle of the array. So this line

position = lst[midpoint]

sets position to N. Then, you never change the value of position!

You should change the two recursive lines to:

return binSearch(lst, what)