What is wrong with my Recursive Binary-Search program?

Question

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.

Some thoughts: ① How dare you name a variable position when in fact it doesn't hold a position. It holds an element instead. ② What is it good for to call binSearch() when you don't use its return value? (You do this in the recursive calls.) ③ You seem to search binary for the element, and as soon as you have found it, you use .index() to find its position. .index() makes a linear search for the element. So all your nice binary searching is useless. — Alfe
– Alfe, Commented Nov 7, 2016 at 1:21
Haha. Sorry about that. Position was suppose to use .index() to find its position in the list. However, to make it easier to understand, I changed it. I still am encountering the same problem if I change it to search index of element position as it gives me N instead of R. — FoolishNumber
– FoolishNumber, Commented Nov 7, 2016 at 1:24
What is your function supposed to return? Is it the element itself or its index in the list? — Paul Rooney
– Paul Rooney, Commented Nov 7, 2016 at 1:28
@PaulRooney The index of the list. However, I adjusted it to see what letter it is returning instead. It still results in the same problem if I look for the index instead as it searchs for the index of N instead of R — FoolishNumber
– FoolishNumber, Commented Nov 7, 2016 at 1:30
@HiDanny the benefit of binary search is that it searches in logarithmic time (i.e. it cuts the field in half on each iteration). Index is a function that just iterates over the entire list, it is linear and thus defeats the object of your binary search. It is not the source of your issue, but it will hamper the performance of your binary search, effectively making it not a binary search. Look here for the python standard library implementation of bisect, which is what you are trying to achieve. — Paul Rooney
– Paul Rooney, Commented Nov 7, 2016 at 1:32

Kittsil · Accepted Answer · 2016-11-07 01:46:23Z

1

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)

answered Nov 7, 2016 at 1:46

Kittsil

2,50715 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

duck · Accepted Answer · 2016-11-07 01:51:30Z

The problem was the syntax

return position

Here is what i got

def binSearch(lst, what,low=0, high=None):
  high = len(lst) if high is None else high
  pos = int(low + (high-low)/len(lst))
  if (pos==len(lst)):
    return False
  elif (lst[pos]==what):
    return pos
  elif high==low:
    return False
  elif (lst[pos]<what):
    return binSearch(lst, what, pos + 1, high)
  else:
    assert lst[pos] > what
    return binSearch(lst, what, low, pos)

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+1) #+1 because the index start from 0
    print (lst[where])
else:
    print("Not found")

Hope it helps.

Thank you for your code. I should have specified that the def binSearch(lst, what) couldn't be changed as it was the template that my professor gave me. However, it seems that your code is an actual binary search unlike mine. Thanks for showing how to do make an actual binary-search!!

jonnyp · Accepted Answer · 2016-11-07 01:51:49Z

The first time through you are going to hit this line of code: position = lst[midpoint] and thus set position to 'N'. Then you recurse through the search, but at each branch you execute: binSearch(lst, what). The 'position' variable in this new, inner binSearch call will in no way affect the position in the outer call. If you want to write the function in this way then that line should really be something like: position = binSearch(lst, what). That should then update the position in the outer call correctly.

Collectives™ on Stack Overflow

What is wrong with my Recursive Binary-Search program?

3 Answers 3

Comments

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Related