Find index of less or equal value in list recursively (python)-CodePudding

got task to find indexes of value and double that value in input list. In input first line we get list range, second - list of values, third - value to find. The output is 2 numbers - indexes of equal or higher value and double the value. If there is none, return -1

Example input:

6
1 2 4 4 6 8
3

Example output:

3 5

What i got so far is standart binary search func, but i dont get how to make it search not only for exact number but nearest higher.

def binarySearch(arr, x, left, right):
    if right <= left:
        return -1
    mid = (left   right) // 2
    if arr[mid] >= x: 
        return mid
    elif x < arr[mid]:          
        return binarySearch(arr, x, left, mid)
    else: 
        return binarySearch(arr, x, mid   1, right)

def main():
    n = int(input())
    k = input().split()
    q = []
    for i in k:
        q.append(int(i))
    s = int(input())
    res1 = binarySearch(q, s, q[0], (n-1))
    res2 = binarySearch(q, (s*2), q[0], (n-1))
    print(res1, res2)

if __name__ == "__main__":
    main()

The input is:

6
1 2 4 4 6 8
3

And output:

3 4

CodePudding user response：

Here's a modified binary search which will return the base zero index of a value if found or the index of the next highest value in the list.

def bsearch(lst, x):
    L = 0
    R = len(lst) - 1
    while L <= R:
        m = (L   R) // 2
        if (v := lst[m]) == x:
            return m
        if v < x:
            L = m   1
        else:
            R = m - 1
    return L if L < len(lst) else -1


data = list(map(int, '1 2 4 4 6 8'.split()))

for x in range(10):
    print(x, bsearch(data, x))

Output: