gistfile1.pyw

from random import randint


def bsearch(stuff, x, offset=0):
    if len(stuff) == 0:
        return -1
    half = int(len(stuff) / 2)
    if stuff[half] == x:
        return half + offset
    elif x < stuff[half]:
        return bsearch(stuff[:half], x, offset)
    elif x > stuff[half]:
        return bsearch(stuff[half + 1:], x, offset + half + 1)


def test(n=100, m=200):
    xs = [randint(0, n) for i in range(m)]
    xs.sort()
    y = randint(0, n)
    print ">>>", y
    i = bsearch(xs, y)
    if (i == -1 and y in xs) or (i != -1 and xs[i] != y):
        print "error -------------------"
        print y, i
        print xs
        print "-------------------------"
    else:
        print "ok"


for i in range(100):
    test()