Search in Rotated Sorted Array

You are given a rotated sorted array of integers and a target integer. The array was originally sorted in non-decreasing order and then rotated at some pivot unknown to you beforehand.

Your task is to find the index of the target in the array. If the target is not present, output -1.

The solution should work in O(log n) time complexity. In particular, consider the scenario when the array is rotated and make use of binary search techniques.

The mathematical condition for the algorithm is based on determining if one of the halves is sorted. For example, if
\(nums[left] \le nums[mid]\) then the left half \(\left[nums[left], nums[mid]\right]\) is sorted. Otherwise, the right half \(\left[nums[mid], nums[right]\right]\) is sorted.

inputFormat

The first line contains an integer n which is the number of elements in the rotated sorted array.

The second line contains n space-separated integers representing the array elements.

The third line contains a single integer target which is the element to search for.

outputFormat

Output a single integer representing the index of the target in the array if it exists; otherwise, print -1.

## sample

7
4 5 6 7 0 1 2
0

4

</p>