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