Teaching Kids Programming – Find Insertion Point in Sorted List via bisect_left or bisect_right

Teaching Kids Programming: Videos on Data Structures and Algorithms

If a list/array sorted, we can find the insertion point/index of given value x via Binary Search Algorithm – which takes O(LogN) time. In Python, we have bisect_left and bisect_right from the package bisect library.

bisect_left

The bisect_left has the following function signature:

bisect_left(a, x, lo=0, hi=None, key=None)

It returns the insertion point i where all elements at a[:i] is strictly smaller than x and all elements at a[i:] are bigger or equal then x. The lo and hi are optional parameters to specify the lower/upper index. The key can be also passed to give a customize key function:

If we go for the linear search, it will take O(N):

def bisect_left(a, x, lo=0, hi=None, key=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    for i in range(lo, hi):
        if key is None:
            v = a[i]
        else:
            v = key(a[i])
        if a[i] >= x:
            return i
    return hi

As the array is already sorted, we can binary search – this improves the time complexity to O(LogN).

def bisect_left(a, x, lo=0, hi=None, key=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi)//2
        if key is None:
            v = a[mid]
        else:
            v = key(a[mid])
        if a[mid] < x: 
            lo = mid+1
        else: 
            hi = mid
    return lo

bisect_right

The bisect_right takes the same parameters but behaves differently. It will return a insertion point i where all elements at a[:i] are smaller or equal to x and all elements at a[i:] are strictly larger than x:

The linear version is quite similar than above:

def bisect_right(a, x, lo=0, hi=None, key=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    for i in range(lo, hi):
        if key is None:
            v = a[i]
        else:
            v = key(a[i])
        if a[i] > x:
            return i
    return hi

and the optimal Binary Search implementation of bisect_right:

def bisect_right(a, x, lo=0, hi=None, key=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi)//2
        if key is None:
            v = a[mid]
        else:
            v = key(a[mid])
        if a[mid] > x: 
            hi = mid
        else: 
            lo = mid + 1
    return lo

–EOF (The Ultimate Computing & Technology Blog) —