Search a Rotated Sorted Array

nums started as a sorted list of distinct numbers, smallest first. Then a block from the front was moved to the back, keeping its order. This is called a rotation. For example, moving the first four numbers of [3, 6, 9, 11, 15, 18, 22] to the back gives [15, 18, 22, 3, 6, 9, 11]. Sometimes nothing was moved, so nums may still be fully sorted.

Find target in nums. Return its index, or -1 if it isn't there.

• You aren't told how many numbers were moved.
• nums can be empty, and it can hold up to 1,000,000 numbers.
• Your solution must take O(log n) time.