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

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:

x = 1 -> -1 (OK)
x = 5 -> 1 (index, wrong)
x = 50 -> 3 (index, wrong)
if x is in the list, the function returns the correct index

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)

CodePudding user response：

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

CodePudding user response：

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)