def BinarySearch(val, A, idx = None):
    """Recursive algorithm for performing binary search"""
    #idx: the rightmost index based on the numbering of the original array

    n = len(A)

    if idx == None:
        idx = (n - 1)

    if n == 1:
        if A[0] == val:
            return idx
        else:
            return -1
    else:
        split = n//2
        if A[split] > val:
            idx -= (n - split)
            return BinarySearch(val, A[:n//2], idx)
        else:
            return BinarySearch(val, A[n//2:], idx)