Problem Statement

Imagine a sorted array that has been rotated at some unknown point. For example, an array like [1,2,3,4,5,6,7] might be rotated to become [5,6,7,1,2,3,4].

Your task is to find the position of a given number within this rotated array. If the number exists in the array, return its index. If not, return -1.

You can assume that all elements in the array are unique.

The solution should have a time complexity of O(log n).

Examples

Example 1:
Array: [5,6,7,1,2,3,4], Number: 2
Output: 4

Example 2:
Array: [5,6,7,1,2,3,4], Number: 8
Output: -1

Constraints

• The length of the array will be between 1 and 20,000.
• All elements in the array are unique integers.
• The number to find will be in the range of -10,000 to 10,000.