def binary_search(array, x):
    """
    Vanilla BS algorithm
    Look for x in the sorted array
    return the index if found
    or else return None


    [8, 9, 10]
    """
    # A: init the low and high values
    low, high = 0, len(array) - 1
    # B: search the array
    while low <= high:
        # find the middle value
        middle = (low + high) // 2
        mid_elem = array[middle]
        # if found, return the index
        if mid_elem == x:
            return middle
        # if not, divide the array into two subproblems
        elif mid_elem < x:  # go right
            low = middle + 1
        elif mid_elem > x:  # go left
            high = middle - 1
    # C: if not found, return None
    return -1