3
\$\begingroup\$

I have a bit of trouble simplifying the binary search code. This is different from the traditional binary search because we effectively want to find the location for which A[j] is the least element larger than the current unsorted value.

Thoughts?

def binary_search(A, value, start, end):
    # we need to distinugish whether we should insert
    # before or after the left boundary.
    # imagine [0] is the last step of the binary search
    # and we need to decide where to insert -1
    if start == end:
        if A[start] > value:
            return start
        else:
            return start+1

    # this occurs if we are moving beyond left's boundary
    # meaning the left boundary is the least position to
    # find a number greater than value
    if start > end:
        return start

    mid = (start+end)/2
    if A[mid] < value:
        return binary_search(A, value, mid+1, end)
    elif A[mid] > value:
        return binary_search(A, value, start, mid-1)
    else:
        return mid

def insertion_sort(A):
    for i in xrange(1, len(A)):
        value = A[i]
        j = binary_search(A, value, 0, i-1)
        A = A[:j] + [value] + A[j:i] + A[i+1:]
    return A

print insertion_sort([0,1,-1])
print insertion_sort([0,1,2,3,9,-1])
print insertion_sort([1,2,3,4,5,6,7,8,11,10,0])
\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

Your binary_search is the same as the built-in function bisect.bisect, and you might find the implementation helpful to study.

\$\endgroup\$
1
  • \$\begingroup\$ Thanks. I always knew bisect has the binary search, didn't think of checking it out first. Thanks though! \$\endgroup\$
    – CppLearner
    Commented Feb 13, 2014 at 21:34

Your Answer

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

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