Solution for snakeeat problem codechef( Getting a TLE)

snakeeat.py

''' Problem link: https://www.codechef.com/problems/SNAKEEAT 
Approach
1: Get the maximum index x for which a[x] < K
2: set the search space for L with lower bound of 0 and upper bound of x+1
3: find the maximum value of l for which eq. K*L - sum(X-L+1,X) <= X-L+1 holds true
'''

def getValue(a,num):
    '''Return the largest value of i for which a[i] < k'''
    low = 0
    high =  len(a)  - 1
    while low < high:
        mid =  int(low + (high - low + 1)/2)

        if a[mid] < num:
            low = mid
        else:
            high = mid - 1
    return low
for i in range(int(input())):
    snakeNum, query = map(int, input().split(' '))
    snakeLenghts = list(map(int, input().split(' ')))
    snakeLenghts.sort()
    sumArray = [] #used to precompute sum of array
    for i in range(len(snakeLenghts)):
        sumArray.append(sum(snakeLenghts[0:i+1]))
    #print(sumArray)
    for i in range(query):
        k = int(input())
        low = 0
        high =  getValue(snakeLenghts,k) 
        x = high

        while low < high:
            ''' predicate condition: K*L - sum(X-L+1,X) <= X-L+1'''
            l =  int(low + ((high + 1) - low)/2)  #number of snakes that have potential to reach k
            tempSum =  sumArray[x] - sumArray[x-l] 
            leftSide = k*l - tempSum
            rightSide = x - l + 1
            if leftSide <= rightSide:
                low = l
            else:
                high =  l - 1
        
        t = (len(snakeLenghts) - 1) - x # number of snake greater then or equalt k
        print(t + low)