Code for two different approaches of percentile computation.

percentileComputations.py

##
#  Naive, brute-force approach.
#    You simply count how many values are smaller than the one for which you want to compute the percentile.
#
def getPercentileOfDensity(density):
    nbInf = 0

    for d in sortedDensities:
        if d < density:
            nbInf+=1 
        else:
            break

    return (nbInf / len(sortedDensities)) * 100

##
#  Dichotomy-based, tail-recursive solution.
#    
#
def getPercentileOfDensityRecTerm(density, densitiesList, lowerBound, higherBound):

    if (higherBound - lowerBound) <= 1:
        return lowerBound

    step = (lowerBound + higherBound)//2
    
    if densitiesList[step] == density:
        return step + 1

    elif densitiesList[step] < density:
        return getPercentileOfDensityRecTerm(density, densitiesList, step+1, higherBound)
    else:
        return getPercentileOfDensityRecTerm(density, densitiesList, lowerBound, step-1)