How do you assign a return value to a variable in python?

Question

I've been working on binary insertion sort and I came across a problem.It keeps telling me that "NoneType' object cannot be interpreted as an integer" at the "binary_insertion_sort" function before the second for loop. Can anyone explain what's wrong with my code and tell me if there's any logic error in it?

def binary_search(n, bin_list, low, high):
    print(low,high)
    if high - low <= 1:
        if n < bin_list[low]:
            return low - 1
        elif n > bin_list[high]:
            print('d',n,high)
            return high + 1
        elif n == bin_list[low]:
            return low
        elif n== bin_list[high]:
            return high
        else:
            print('c',low)
            return low+1
    mid = (low+high)//2
    print('a',mid)
    if n < bin_list[mid]:
        binary_search(n, bin_list, 0, mid-1)
    elif n > bin_list[mid]:
        binary_search(n, bin_list, mid+1, high)
    else:
        return mid

the binary_insertion_sort part

def binary_insertion_sort(text):
    sorted_list = text.split()
    for num in range(1, len(sorted_list)):
        unsorted = sorted_list[num]
        print(sorted_list)
        index = binary_search(unsorted, sorted_list, 0, len(sorted_list)-1)
        for  j in range(num, index, -1):
            print(j)
            sorted_list[j] = sorted_list[j-1]
            sorted_list[index-1] = num
    return sorted_list

a = binary_insertion_sort('1 2 3 4 5')

Answer 1

I think you are missing the returns for the recursive cases in the binary_search function.

As the function enters one of the first two cases in the last if:

if n < bin_list[mid]:
    binary_search(n, bin_list, 0, mid-1)
elif n > bin_list[mid]:
    binary_search(n, bin_list, mid+1, high)
else:
    return mid

You are assigning None (the function return type) to the index var. You should try using:

if n < bin_list[mid]:
    return binary_search(n, bin_list, 0, mid-1)
elif n > bin_list[mid]:
    return binary_search(n, bin_list, mid+1, high)
else:
    return mid