A.k.a. bisection search.
def binary_search(list, item):
""" binary_search returns the position (index) of
item in a SORTED list or None if not found.
"""
# Which part of the list to search. At the
# beginning it's the entire list.
low = 0
high = len(list) - 1
while low <= high: # While window is open
mid = int((low+high)/2) # try middle element.
guess = list[mid]
if guess == item: # we've found the item
return mid
if guess > item: # guess was too high
high = mid - 1
else: # guess was too low
low = mid + 1
return None # the item not found
More
- MIT OpenCourseWare (video)
- My Perl and Go implementation