Binary Insert Method - handling edge cases 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 &lt; a[min]:
        return -1
    if x &gt; a[max-1]:
        return max

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

    # Another edge case
    return min if a[min] &gt;= 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 &lt; 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
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.