Binary Insert Method - handling edge cases

Question

I've created a function that uses binary search to insert an element into an array (similar to this question). I haven't benchmarked it, but based on my knowledge it should get \$O(1)\$ in the best case (i.e., appending an item to the end of the list) and \$O(nlogn)\$ in the average/worst case (I have no numbers to back this up - frankly I don't have much experience with benchmarking, so have mercy on me.)

Here's the binary search algorithm:

def binary_search(a, x):
    mid = 0
    min = 0
    max = len(a)

    # Deal with the edge cases
    if x < a[min]:
        return -1
    if x > a[max-1]:
        return max

    # Now that we know that the value is in range,
    # perform the actual search
    while min < max:
        mid = mid_point(min,max)
        if x < a[mid]:
            max = mid - 1
        elif x > a[mid]:
            min = mid + 1
        else:
            return mid

    # Another edge case
    return min if a[min] >= x else min + 1

This will return the index to insert the element into. The function used to perform the insertion is simple:

def binary_insert(array, value):
    index = binary_search(array,value)
    if index < 0: # Just append the value to the end of the list
        array.insert(0,value)
    else:
        array.insert(index,value)

The function works on a pre-sorted list (a requirement of a binary search) and maintains the list in sorted order. For example inserting [0..10) (aka [0,1,2,...,8,9]) into [-1, 0, 1, 4, 5, 6, 7, 8, 9, 10] yields [-1, 0, 0, 1, 1, 2, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10]

You may have noticed that the return statement (the last one) for binary_search is very messy, and not very intuitive. Would like to be able to incorporate that logic into the while loop somehow, or at least simplify it. Does anyone have an idea of how I could do this? (Side question: how do I benchmark this?)

EDIT:

This is the mid_point function.

def mid_point(x, y):
    return (x+y)/2

Answer 1

If you want to go deep into the implementation of binary search and insertion, my advice is to take a look at the bisect module in the standard library:

def insort_left(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.

    If x is already in a, insert it to the left of the leftmost x.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    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 a[mid] < x: lo = mid+1
        else: hi = mid
    a.insert(lo, x)


def bisect_left(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(x) will
    insert just before the leftmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    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 a[mid] < x: lo = mid+1
        else: hi = mid
    return lo

Answer 2

Here are some thoughts:

For benchmarking there are two modules folks usually use:

cProfile

bettertimeit

I put an example in a previous post located here:

Profiling

Also, can you please post the entire script? Just want to make sure I have full context. Namely mid_point.