Untitled

def my_bisect(v, x, lo=0, hi=None, alg="left"):

    # bisect an already sorted v in range [lo, hi). result can in in [lo, hi]

    # alg = 'left' to compute lower bound (first occurence or where x should be)

    # alg = 'right' to compute upper bound (successive of last occurence or where x should be)

    # returns hi if x is greater than v[-1], 0 if lower than v[0]

 

    # default last index (exclusive)

    hi = hi if hi is not None else len(v)

 

    # recursion base case

    if lo >= hi:

        return lo

 

    mid = (lo + hi) // 2

 

    # if x > v[mid], mid can't be the result

    # also the case if v[mid] = x and alg = 'right'

    if v[mid] < x or (v[mid] == x and alg == "right"):

        return my_bisect(v, x, mid + 1, hi, alg)

    else:

        # NB can return mid

        return my_bisect(v, x, lo, mid, alg)