Rotated Array Search

You have an array that was sorted and then rotated at some pivot. Given the rotated array and a target value, return the index of the target value in the array, or -1 if it is not found. Input: The first line contains n (1 <= n <= 10^5), the length of the array. The second line contains n space-separated integers in the rotated array. The third line contains the target integer. Output: Return the index of the target in the array, or -1 if it is not found. Example: Input: 7 4 5 6 7 0 1 2 0 Output: 4