def magic_index(arr):
    """ 8.3 Magic Index: A magic index in an array A [ 0... n -1] is defined
    to be an index such that A[i] = i.
    Given a sorted array of distinct integers, write a method to find a magic
    index, if one exists, in array A.

    FOLLOW UP
    What if the values are not distinct?

    For distinct values we can recurse on the half of the array which is smaller,
    all the time. For non-distinct values, we have to recurse on all elements.
    """
    def rec_magic_index(arr, left, right):
        if right < left:
            return []
        if right - left == 0:
            if arr[right] == right:
                return [right]
            else:
                return []

        middle = (right + left) / 2
        left_magic_indices = rec_magic_index(arr, left, middle)
        right_magic_indices = rec_magic_index(arr, middle + 1, right)
        return left_magic_indices + right_magic_indices

    return rec_magic_index(arr, 0, len(arr) - 1)