1
\$\begingroup\$

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
\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ Is this the code used by the module? (I never knew about the // operator, that's cool) \$\endgroup\$
    – sotrh
    Jul 15, 2014 at 19:36
  • \$\begingroup\$ @sotrh Yes, that's the code in python 2.7.6 stdlib. Note that // is floor division whose behavior is consistent in python 2 and 3, but regular / doesn't behave the same way. More information here. \$\endgroup\$
    – jcollado
    Jul 15, 2014 at 21:34
  • \$\begingroup\$ So basically insort_left and bisect_left do the same thing except insort_left inserts x into the list while bisect_left just returns where it should be inserted? \$\endgroup\$
    – sotrh
    Jul 15, 2014 at 21:43
  • \$\begingroup\$ @sotrh Correct. As pointed out by the documentation bisect.insort_left is equivalent to a.insert(bisect.bisect_left(a, x, lo, hi), x) \$\endgroup\$
    – jcollado
    Jul 15, 2014 at 21:53
  • \$\begingroup\$ It's good to know about this module. I wrote my code as a mock which I'll use to write the java equivalent \$\endgroup\$
    – sotrh
    Jul 15, 2014 at 21:57
1
\$\begingroup\$

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.

\$\endgroup\$
8
  • \$\begingroup\$ I updated the post to include mid_point \$\endgroup\$
    – sotrh
    Jul 15, 2014 at 18:25
  • \$\begingroup\$ I didn't know about bettertimeit, thanks. \$\endgroup\$
    – jcollado
    Jul 15, 2014 at 19:05
  • \$\begingroup\$ I tried the bettertimeit module using the code from your other answer, but I'm getting ImportError: No module named bettertimeit when I try to run it. \$\endgroup\$
    – sotrh
    Jul 15, 2014 at 19:44
  • \$\begingroup\$ I'm running python 2.7.6 by the way. \$\endgroup\$
    – sotrh
    Jul 15, 2014 at 19:45
  • \$\begingroup\$ @sotrh bettertimeit is not part of the stdlib. Your probably need to install it. \$\endgroup\$
    – jcollado
    Jul 15, 2014 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.