Given a rotated sorted array nums (with distinct values) and a target, return the index of target or -1 if not found.
You must achieve O(log n) time complexity.
Example:
Input:
4,5,6,7,0,1,2
0
Output:
4
Reasoning:
The given array is rotated, so we need to find the pivot point where the rotation occurred.
We use a modified binary search algorithm to achieve O(log n) time complexity, dividing the search space in half at each step.
The target value 0 is less than the middle element of the array, so we repeat the search in the right half of the array: [0,1,2].
Since 0 is found at the first position of the right half, which is the 4th index in the original array (using 0-based indexing), the function returns 4.