Search in Rotated Sorted Array

Given a rotated sorted array of integers, your task is to determine the index of a target integer using an efficient algorithm. The array is sorted in ascending order, but it is rotated at some unknown pivot. You must implement a solution that returns the index of the target if it is present in the array, or -1 if it is not.

This problem can be efficiently solved using a modified binary search algorithm. Consider the following idea: if the array is rotated, then one half of the array remains sorted. By comparing the target with the sorted half, you can decide whether to move to the left or right segment.

The algorithm can be conceptually represented as: $$ index = f(\text{nums}, \text{target}) $$ where \( f \) denotes the search algorithm.

inputFormat

The input is read from standard input (stdin) and consists of two lines. The first line contains a list of space-separated integers representing the rotated sorted array. The second line contains a single integer representing the target value.

outputFormat

Output to standard output (stdout) a single integer representing the index of the target element in the array, or -1 if the target does not exist.## sample

4 5 6 7 0 1 2
0

4