# Arup Guha
# 6/28/2017
# Solution to 2017 SI@UCF Python wRecursion Test #2 Question 3

def main():

    testlist = [2, 3, 3, 3, 4, 5, 12, 13, 22, 97, 121, 2005]
    print(numAtOrBelow(testlist, 0, 11, 15))
    print(numAtOrBelow(testlist, 0, 11, 22))
    print(numAtOrBelow(testlist, 0, 11, 2))
    print(numAtOrBelow(testlist, 0, 11, 1))
    print(numAtOrBelow(testlist, 0, 11, 2005))
    print(numAtOrBelow(testlist, 0, 11, 10000000))
    print(numAtOrBelow(testlist, 3, 7, 15))
    print(numAtOrBelow(testlist, 3, 7, 2))
    print(numAtOrBelow(testlist, 3, 7, 3))
    print(numAtOrBelow(testlist, 2, 9, 3))
    
def numAtOrBelow(mylist, low, high, target):

    # Empty range return nothing.
    if low > high:
        return 0

    mid = (low+high)//2

    # Everything is in left half - just go there.
    if target < mylist[mid]:
        return numAtOrBelow(mylist, low, mid-1, target)

    # All left half should be counted - add that to right half result.
    else:
        return mid-low+1 + numAtOrBelow(mylist, mid+1, high, target)

main()