"""
Search for a given number in a sorted array, with unique elements, that has been rotated by some arbitrary number. Return -1 if the number does not exist.
"""

# iterative
def binary_search_rotated(arr, key):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = low + ((high - low) // 2)

        if arr[mid] == key:
            return mid

        # sorted parts
        if arr[low] <= arr[mid] and key >= arr[low] and key <= arr[mid]:
            high = mid - 1

        elif arr[mid] <= arr[high] and key >= arr[mid] and key <= arr[high]:
            low = mid + 1

        # unsorted parts
        elif arr[low] >= arr[mid]:
            high = mid - 1

        elif arr[mid] >= arr[high]:
            low = mid + 1

    return -1


# recursive
def binary_search_rotated(arr, key):
    return binary_search(arr, key, 0, len(arr) - 1)


def binary_search(arr, key, low, high):
    if low > high:
        return -1

    mid = low + ((high - low) // 2)

    if arr[mid] == key:
        return mid

    # sorted parts
    if arr[low] <= arr[mid] and key >= arr[low] and key <= arr[mid]:
        return binary_search(arr, key, low, mid - 1)

    elif arr[mid] <= arr[high] and key >= arr[mid] and key <= arr[high]:
        return binary_search(arr, key, mid + 1, high)

    # unsorted parts
    elif arr[low] >= arr[mid]:
        return binary_search(arr, key, low, mid - 1)

    elif arr[mid] >= arr[high]:
        return binary_search(arr, key, mid + 1, high)
