CODE EXAMPLE FOR PYTHON

python binary search

from bisect import bisect_right, bisect_left

'right border index := index of leftmost value > x'
bisect_right(arr, x)  # may be equal to len(arr)

'left border index := index of rightmost value < x'
bisect_left(arr, x) - 1  # may be equal to -1

def first_occurence(a, x):  # equal to a.index(x) but faster
    'Locate the leftmost value = x'
    i = bisect_left(a, x)
    if i == len(a) or a[i] != x:
        raise ValueError
    return i

def last_occurence(a, x):
    'Locate the rightmost value = x'
    i = bisect_right(a, x) - 1
    if i == -1 or a[i] != x:
    	raise ValueError
    return i