Biased Binary Sort Return First Index of Insertion

  binary-search, python, recursion

I am trying to make a way of returning the first possible location where I can insert a new term in an increasing list. My general attempt is to use binary sort until the condition arises that the term before is less than my inserting term, and the next term is equal to or greater than my inserting term:

lis = [1,1,2,2,2,4,5,6,7,8,9]

def binary_sort(elem, lis, left, right):

    mid = (left + right)//2
    if (lis[mid-1] < elem and elem <= lis[mid]):
        return mid
    elif (lis[mid] > mid):
        return binary_sort(elem, lis, mid, right)
    else:
        return binary_sort(elem, lis, left, mid)

This is not working… where is the issue with my code or my general strategy?

Source: Python Questions

LEAVE A COMMENT