def binarySearch(L, k, left, right):
    # Base case 1: element not found
    if left > right:
        return -1

    mid = (left + right)/2 # index of the middle element

    # Base case 2: element found at the midpoint
    if L[mid] == k:
        return mid # element is found at mid, so return this index
    
    # Recursive cases: we search in left half or right half
    elif L[mid] < k: # look for element in right half
        return binarySearch(L, k, mid+1, right)
    
    elif L[mid] > k: # look for element in the left half
        return binarySearch(L, k, left, mid-1)