A sorted array was rotated at some pivot. Given this rotated array nums and a target, return the index of target or -1 if not found.
With nums = [4, 5, 6, 7, 0, 1, 2] and target = 0, the answer is 4. The original sorted array [0, 1, 2, 4, 5, 6, 7] was rotated, and 0 now sits at index 4.
Standard binary search won't work directly. How can you adapt it when the array is only partially sorted?
Constraints: . All values unique. Must run in .