Algorithms for Coding Interviews in Python/

...

/

Solution: Search Position

Solution: Search Position

Let's look at a detailed analysis of the different ways to find the position to insert an element in a list.

We'll cover the following...

Solution: modified binary search

Python 3.5
def search_insert_position(lst, value):
    """
    A function to search insert position of a given value in a list
    :param lst:  A list of integers
    :param value: An integer
    :return: The position of the value to be in the list
    """
    size = len(lst)
    if size < 1:
        return -1
    start = 0
    end = size - 1
    pos = 0
    while start <= end:
        mid = start + (end - start) // 2
        if lst[mid] == value:
            return mid
        elif lst[mid] > value:
            end = mid - 1
            pos = mid
        else:
            start = mid + 1
            pos = mid + 1
    return pos
# Driver to test above code
if __name__ == '__main__':
    lst = [1, 3, 5, 6]
    value = 5
    print(search_insert_position(lst, value))
    value = 2
    print(search_insert_position(lst, value))

Explanation

This solution is a simple modification of the binary search algorithm. It simply keeps track of the variable, mid, with another one, pos.

Time

...