binary_search.py

def binary_search(seq, obj):
    low, high = 0, len(seq) - 1
    while low <= high:
        mid = low + ((high - low) / 2)
        order = cmp(seq[mid], obj)
        if order is 0:
            return mid
        elif order > 0:
            high = mid - 1
        else:
            low = mid + 1
    return -1

def search(seq, obj):
    print "Input: %s" % seq
    seq = sorted(seq)
    print "Searching %s in %s." % (obj, seq)
    p = binary_search(seq, obj)
    if p < 0:
        print "Not Found."
        return False
    else:
        assert seq[p] == obj
        print "Found at %d (%s)" % (p, seq[p])
        return True

assert search([1, 4, 3, 5, 56, 7, -1, 66, 890, 165, 57, 1], 66)
assert search("Hello, World!", "e")
assert not search([], 1234)
assert search([1, 2, 3, 4], 1)
assert search([1, 2, 3, 4], 4)
assert search([1, 2, 3], 2)
assert search([1, 1, 1, 1, 1], 1)