# Uses a binary search algorithm to find the index of the maximum element in
# a bitonic sequence

def findBitonicMax(L, first, last):
    # Base case: list L[first:last+1] has exactly one element
    if first == last:
        return first

    # Base case: list L[first:last+1] has exactly two elements
    if first + 1 == last:
        if L[first] < L[last]:
            return last
        else:
            return first
        
    # Recursive case: last > first + 1; list L[first:last+1] has more than 2 elements
    mid = (first + last)/2
    
    # Element at mid is the largest
    if L[mid] > L[mid-1] and L[mid] > L[mid+1]:
        return mid
    
    # mid is in ascending part of the sequence
    if L[mid-1] < L[mid] and L[mid] < L[mid + 1]:
        return findBitonicMax(L, mid+1, last)
    
    # mid is in descending part of the sequence
    if L[mid-1] > L[mid] and L[mid] > L[mid + 1]:
        return findBitonicMax(L, first, mid-1)

# if isAscending is True, then we should search for k to the left of mid
# if k < L[mid]; otherwise, if isAscending is False, then we should search for
# k to the left of mid if k > L[mid]
def onLeft(L, mid, k, isAscending):
    if isAscending:
        return k < L[mid]
    else:
        return k > L[mid]

# This is the binary search function we discussed in class, except that
# it takes as an extra argument a boolean argument called isAscending that
# indicates if the list is in ascending order or not
def binarySearch(L, k, first, last, isAscending):
    # Base case
    if first > last:
        return False
    
    # Recursive case
    mid = (first + last)/2
    if L[mid] == k:
        return True
    elif onLeft(L, mid, k, isAscending):
        return binarySearch(L, k, first, mid-1, isAscending)
    else:
        return binarySearch(L, k, mid+1, last, isAscending)

# Determines if k is in L[first:last+1]; returns True if this is the case, False
# otherwise
def searchBitonic(L, k, first, last):
    maxIndex = findBitonicMax(L, first, last)
    if L[maxIndex] == k:
        return True
    
    return binarySearch(L, k, first, maxIndex-1, True) or binarySearch(L, k, maxIndex+1, last, False)