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