def problem_9_3(arr, key):
    """ Given a sorted array of n integers that has been rotated an unknown
    number of times, give an O(log n) algorithm that finds an element in the
    array. You may assume that the array was originally sorted in increasing
    order.

    Example:
    Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14)
    Output: 8 (the index of 5 in the array)

    Solution: There are two rotation cases:
    i.  [8,9,1,2,3,4,5,6,7] - inflexion point is before middle.
    ii. [3,4,5,6,7,8,9,1,2] - inflexion point is after middle.

    Use modified divide and conquer binary search. There are 8 cases
    defined by comparing the key with left, right and middle positions. Thus
    identify the rotation case and recurse on the appropriate array.
    """
    def modified_binary_search(arr, key, left, right):
        if left > right:
            return None

        middle = (left + right) / 2

        if arr[middle] == key:
            return middle

        if arr[left] <= arr[middle]:
            if key > arr[middle]:
                return modified_binary_search(arr, key, middle+1, right)
            elif key >= arr[left]:
                return modified_binary_search(arr, key, left, middle-1)
            else:
                return modified_binary_search(arr, key, middle+1, right)
        elif key < arr[middle]:
            return modified_binary_search(arr, key, left, middle-1)
        elif key <= arr[right]:
            return modified_binary_search(arr, key, middle+1, right)
        else:
            return modified_binary_search(arr, key, left, middle-1)
        return None

    return modified_binary_search(arr, key, 0, len(arr) - 1)