Recursive binary search python

Question

I've been trying to write binary search recursively. When I do this using the list[:] syntax I don't get the intended results with several errors coming up or not getting the correct values.

def binary_search(arr, val):

  left = 0 
  right = len(arr)-1
  mid = (left + right)//2

  #Go through the array
   if (val == arr[mid]):
     return mid
   #Check right side of arr
   if (val > arr[mid]):
     return binary_search(arr[mid+1:], val)
   #Check left side of arr
   return binary_search(arr[:mid], val)

EDIT: Example inputs and outputs

arr1 =[]
for i in range(10):
    arr1.append(i)

for i in range(10):
    print(binary_search(arr1,i))

I expect to get something like '0,1,2,3,4,5,6,7,8,9' but get '0,1,0,0,4,None ,None,2,0,0'

Answer 1

You have two problems. First one is a typo, where you say

if (val > mid):

you should say

if (val > arr[mid]):

Since you're comparing the value and not the index.

Second one is more subtle... when you check the right side of the array, in:

return binary_search(arr[mid+1:], val)

The subarray you're passing to the recursive call (arr[mid+1:]) already starts in the middle of the array, that means the result of that recursive call will return the index of the element in the subarray. So you need to add the index delta you used to split the array, to have a index based on the full array again:

return binary_search(arr[mid+1:], val) + (mid + 1)

Here's the full code for completeness:

def binary_search(arr, val):
  left = 0 
  right = len(arr)-1
  mid = (left + right)//2

  #Go through the array
  if (val == arr[mid]):
     return mid
   #Check right side of arr
  if (val > arr[mid]):
     return binary_search(arr[mid+1:], val) + (mid + 1)
   #Check left side of arr
  return binary_search(arr[:mid], val)