There is an integer array `nums` sorted in ascending order (with distinct values). Prior to being passed to your function, `nums` is possibly rotated at an unknown pivot index.
Given the array `nums` and an integer `target`, return the index of `target` if it is in `nums`, or `-1` if it is not in `nums`.
You must write an algorithm with `O(log n)` runtime complexity.
### Constraints
- `1 <= nums.length <= 5000`
- `-10^4 <= nums[i] <= 10^4`
- All values of `nums` are unique.
- `-10^4 <= target <= 10^4`
### Input Format
First line contains space-separated integers representing `nums`.
Second line contains a single integer `target`.
### Output Format
Print the integer index of `target`, or `-1` if not found.
Sample Cases
Example 1Sample Case
Input: 4 5 6 7 0 1 2
0
Output: 4
Example 2Sample Case
Input: 4 5 6 7 0 1 2
3
Output: -1
Example 3Sample Case
Input: 4 5 6 7 0 1 2
6
Output: 2
Example 4Sample Case
Input: 4 5 6
9
Output: -1
Constraints
Runtime Limit: 2000 ms per test batch
Memory Limit: 256 MB
Standard I/O stream reading
Official submissions are evaluated against hidden test cases on the server to verify time & memory complexity.