Biased Binary Sort Return First Index of Insertion

Question

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?

Answer 1

I would suggest to take a look at the following code.

def binary_insertion_search(elem, items, left, right):
    if elem > items[right]:
        return right + 1
    while left < right:
        mid = (left + right) // 2
        if elem > items[mid]:
            left = mid + 1
        elif elem <= items[mid]:
            right = mid
    return left

I rewrote your function a little bit. Now for the explanation:

I assumed that the index to return is the first position that any content can be placed at, which in turn would move all following items to the right.

Since we can not incorporate indices outside of the range of the list by design, we have to check if the element is larger than the item at the end of the list. We then return the next possible index len(lis).

To avoid recursion alltogether, I used a while loop. First, we check, whether left is equal to or greater than right. This can only be true, if we have found the index to put the element at.

Your calculation of the mid value was good, so I just kept it.

If our element is greater than the item at mid, the only possible next option is to select the next unchecked position, which is mid + 1.

Now for the interesting part. Like in the other case, to find the leftmost item, we have to set the right boundary to mid - 1, in order to skip the mid element. However, we check if the element is smaller or equal to the item at mid. This guarantees us that when we find a candidate that is equal to the searched element, we run the search again (with reduced ranged from right) to possibly find a smaller index. This stops, when left == right is true, ending the loop.

I hope this answers your question and points out the differences in the code!