# Given sorted list A and element x, return index of m in A or None.
# Precondition: A is sorted
def binary_search(A, x):
    """ Given sorted list A and element x, return index of m in A or None
    >>> binary_search([1,2,3,4,5], 1)
    0
    >>> binary_search([1,2,3,4,5], 5)
    4
    >>> binary_search([1,2,2,4], 2)
    1
    >>> binary_search([1,2,3,4,5], 42)

    >>> binary_search([], 0)

    """
    l = 0
    r = len(A)-1
    m = (l+r) // 2

    while l <= r and A[m] != x:
        if x < A[m]:
            r = m-1
        else: # x > A[m]
            l = m+1
        m = (l+r)//2

    if l<=r:
        return m

    return None  # kinda redundant


# "Main" entry point
if __name__ == "__main__":
    import doctest
    doctest.testmod()