Rotated Array Search

You are given a rotated sorted array of unique integers and a target integer. A rotated sorted array is an array that has been sorted in increasing order and then rotated by some pivot unknown to you beforehand. For example, the array [4, 5, 6, 7, 0, 1, 2] is a rotated version of the sorted array [0, 1, 2, 4, 5, 6, 7].

Your task is to find the index of the target element in the array. If the target does not exist in the array, output -1. The algorithm should achieve a time complexity of $O(\log n)$ using a modified binary search.

inputFormat

The input is read from standard input and consists of three lines:

1. The first line contains an integer n denoting the number of elements in the array.
2. The second line contains n space-separated integers representing the rotated sorted array.
3. The third line contains an integer target which is the value to search for.

outputFormat

Output a single integer to standard output, which is the index of the target if it exists in the array; otherwise, output -1.

Note: The array indices are 0-based.

7
4 5 6 7 0 1 2
0

4