CODEWITHSUNDEEP
pythonrecursionbinary-searchlocal-variables
David Barnwell
David Barnwell

Reputation: 1

Python recursive binary search function not working but cannot see why

all this is my first time posting here. I've got a recursive binary search function which should work. But isn't. It has an if condition that uses the 'or' logical operator to test whether a key is outside the bounds of an input array. That seems to be the source of the problem. The if condition works outside my recursive function but doesn't seem to work inside it. It's most likely a small issue but I cannot see what that issue could be

 A = [31,48,59,62,71,75,81]
 L=0
 R=len(A)-1
 key = 71

 def recur_binary_search(A, L, R, key):
   if key < A[L] or key > A[R]:
     return -1
   M = (L + R) // 2
   if key < A[M]:
     return recur_binary_search(A,L,M-1,key)
   elif key > A[M]:
     return recur_binary_search(A,L,M+1,key)
   else:
     return M

 print( recur_binary_search(A, L, R, key))
 # my code keeps returning -1 rather than the correct value, 4.

I expected an output of 4, but I keep getting a value of -1 returned. This seems to be caused by this if condition

if key < A[L] or key > A[R]:
    return -1

But, I just cannot see how that if condition, could ever evaluate to true at the start of the function. My function can see A[L] which is 31. It can see A[R] which is 81 (verified via print statements) and it can see the key. The key is 71.

So, how is this if evaluating to true? As I said, I'm sure it is a small issue but I can't see what it is.

Upvotes: 0

Views: 66

Answers (5)

nulzo
nulzo

Reputation: 106

It seems that your logic when you recurse is a bit off. When you find that the key < A[M], then (following the code you provided), you need to return recur_binary_search(A, L, M-1, key) because you want to set your right value to middle-1. Similarly, if you find that key > A[M] you will want to return recur_binary_search(A,M-1,R,key) because you want to set your left value to middle-1.

Your general algorithm right now is only modifying your right value, and this is why you are always returning -1. Hopefully this provides insight into how to properly perform a recursive binary search (while still sticking to the general shape of the code you sent). Let me know if you need any further clarification.

Upvotes: 1

David Barnwell
David Barnwell

Reputation: 1

Hey y'all I found the problem. Thanks for helping. I messed up the boundaries on the second recursion call. (I almost slapped myself when I realized. lol)

def recur_binary_search(A, L, R, key):
  if key < A[L] or key > A[R]:
    return -1
  else: 
   M = (L + R) // 2
  if key < A[M]:  
     return recur_binary_search(A,L,M-1,key)
  elif key > A[M]:    
    return recur_binary_search(A,M+1,R,key) # the fix
  else:
    return M

Upvotes: 0

nmbr73
nmbr73

Reputation: 31

You said you used print to verify your inputs; then I'd recommend to add a print statement at the beginning of your function to see exactly what's happening ...

[...]
def recur_binary_search(A, L, R, key):
  print(f"{L=}, {R=}, {key=}, {A[L]=}, {A[R]=}, {(L + R) // 2=}")
  if key < A[L] or key > A[R]:
    return -1
[...]

... gives ...

L=0, R=6, key=71, A[L]=31, A[R]=81, (L + R) // 2=3
L=0, R=4, key=71, A[L]=31, A[R]=71, (L + R) // 2=2
L=0, R=3, key=71, A[L]=31, A[R]=62, (L + R) // 2=1
-1

... so your A[M] never is 71; resp. you don't get the 4 that you expect because M never is 4.

That should be enough of a hint and for an answer to the "see why" of your question ... I don't want to spoil the solution - good luck and have fun!

Upvotes: 0

achrafhamid
achrafhamid

Reputation: 76

try this:

A = [31,48,59,62,71,75,81]
key = 71

  
def recurs_binary_search(A,L,R,key):
    if L<=R:
        M=(L+R)//2
        if key<A[M]:
            return recurs_binary_search(A,L,M-1,key)
        elif key>A[M]:
            return recurs_binary_search(A,M+1,R,key)
        else:
            return M
    else:
        return -1
 

recurs_binary_search(A,0,len(A)-1,key)
4

Upvotes: 1

Max
Max

Reputation: 1

The reason why it is returning -1 instead of 4 is because the or operator is for boolean if statements. The or operator checks if any of the statements (key < A[L] and key > A[R]) are true. If it is true, than the if statement will go on to complete the code after it (return -1). If false, than the if statement will break. If you want to have more than 1 function checked, than you have to add a elif or another if.

Upvotes: -1

Related Questions