Rotated Sorted Array Search

You are given a rotated sorted array of distinct integers. The array was originally sorted in ascending order, but it was rotated at some unknown pivot index. Your task is to write a program to search for a target value in this array and return its index. If the target is not found, output -1.

The problem can be formalized as follows:

Given an integer array \( \textbf{nums} \) of length \( n \) that has been rotated at an unknown pivot, and a target value \( t \), determine the index of \( t \) in \( \textbf{nums} \) using an algorithm with \( O(\log n) \) time complexity. If \( t \) is not present in the array, return \( -1 \).

inputFormat

The input is read from standard input (stdin) and consists of three parts:

1. An integer \( n \) representing the number of elements in the array.
2. A line with \( n \) space-separated integers representing the rotated sorted array.
3. An integer representing the target value \( t \).

outputFormat

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

7
4 5 6 7 0 1 2
0

4