def binsearch(list, elt):
    """
    Perform a recursive binary search to determine if elt is in the given list. 
    Return True if it is, False otherwise.
    """
    return binsearch_helper(list, 0, len(list)-1, elt)

def binsearch_helper(list, i, j, elt):
    """
    Perform a recursive binary search to determine if elt is in list[i:j+1]. 
    Return True if it is, False otherwise. This version of binsearch does not
    create new copies of the list (unlike the version in your textbook). 
    """
    if j < i:
        return False
    
    mid = (i+j) / 2
    
    if list[mid] == elt:
        return True
    
    if elt > list[mid]:
        return binsearch_helper(list, mid+1, j)
    
    else:
        return binsearch_helper(list, i, mid-1)
    
def binsearch_it(list, elt):
    """Perform an iterative binary search to determine if elt is in the given
    list. Return True if it is, False otherwise."""
    i = 0                       # left index of search
    j = len(list)-1             # right index of search
    while i <= j:               

        # check if the element is at the midpoint in list[i:j+1]. If it's not
        # then adjust the range of the search appropriately. 
        
        mid = (i+j)/2           
        if list[mid] == elt:
            return True
        if elt > list[mid]:       # element must be in second half
            i = mid+1
        else:                     # element must be in first half
            j = mid-1
            
    return False