Skip to content

Instantly share code, notes, and snippets.

/gist:371496

Created Apr 19, 2010
Embed
What would you like to do?
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment