Binary Search

Time Complexity: O(log n)

n = len(array)

# array sorted in ASC
# If the target exists, returns its leftmost index.
# Else, returns the index of where it should be.
def binarySearch(array, target):
    l, r = 0, len(array)
    while l < r :
        m = (l + r) // 2
        if array[m] < target:
            l = m + 1
        else:
            r = m
    return l