Search in Rotated Sorted Array

You are given a rotated sorted array, i.e. an array that was originally sorted in ascending order and then rotated at an unknown pivot. You need to search for a given target value in the array and return its index. If the target is not present in the array, output -1.

Your solution should ideally run in \(O(\log n)\) time. Use binary search concepts to find the target even when the array is rotated.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer \(n\) representing the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the rotated sorted array. If \(n = 0\), this line may be empty.
• The third line contains an integer representing the target value to search for.

outputFormat

Output a single integer to standard output (stdout): the index of the target in the array if it exists, otherwise output -1.

7
4 5 6 7 0 1 2
0

4