Skip to content

Instantly share code, notes, and snippets.

@teepark

teepark/bsearch.py

Created Apr 19, 2010
Embed
What would you like to do?
def bsearch(lst, item):
bottom, top = 0, len(lst)
while top - bottom >= 3:
mid = (top + bottom) // 2
c = cmp(item, lst[mid])
if c < 0:
top = mid
elif c > 0:
bottom = mid + 1
else:
return True
if item == lst[bottom]:
return True
return top - bottom == 2 and item == lst[bottom + 1]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment