CODEWITHSUNDEEP
pythonrecursion
tetris555
tetris555

Reputation: 315

Validation in recursive Python function is met, but after that execution continues on else statemen

I am confused why after the condition is met and executed, the function does not return -1 but instead continues on the else statement.

if len(arr) == 1 and arr[mid] != n: return -1

given array = [2, 3, 4, 10, 40] and if:

When I run the debugger, eventually, the array gets down to 1 element but if statement does not work as I expect. Where is my mistake, thanks?

def binary_search(arr, n):

# if n not in arr:
#     return -1


  mid = len(arr) // 2

  if len(arr) == 1 and arr[mid] != n:
      return -1

  elif n == arr[mid]:
      return mid  

  elif n < arr[mid]:
      return binary_search(arr[:mid], n)

  else:
      return mid + binary_search(arr[mid:], n)

Upvotes: 0

Views: 33

Answers (2)

tetris555
tetris555

Reputation: 315

After Chris Doyle answered, I changed the function in the following way, and it seems to work correctly now:

def binary_search(arr, n, idx=0):

  mid = len(arr) // 2

  if len(arr) == 1 and arr[mid] != n:
      return -1

  elif n == arr[mid]:
      return idx + mid

  elif n < arr[mid]:
      return binary_search(arr[:mid], n, idx)

  else:
      return binary_search(arr[mid:], n, idx + mid)

Upvotes: 0

Chris Doyle
Chris Doyle

Reputation: 12199

your else statement adds the mid point index to the returned value of binary_search. So once you get to the last element, you return -1 up the stack, then you add that return value to the mid point in the previous stack which was 1. So you then return -1 + 1 which is 0, so you return 0 to the last stack where the mid point was 2, so you return 2 + 0 which is 2.

def binary_search(arr, n):
    # if n not in arr:
    #     return -1

    mid = len(arr) // 2

    if len(arr) == 1 and arr[mid] != n:
        return -1

    elif n == arr[mid]:
        return mid

    elif n < arr[mid]:
        return binary_search(arr[:mid], n)

    else:
        return binary_search(arr[mid:], n)

print(binary_search( [2, 3, 4, 10, 40], 11))

-1

Upvotes: 1

Related Questions