Search in Rotated Sorted Array

You are given an integer array nums sorted in ascending order (with distinct values), then rotated at some unknown pivot index. Given nums and an integer target, return the index of target in nums, or -1 if it is not present. You must write an algorithm with O(log n) runtime complexity.

Input / output

• Input: nums: integer[] (rotated ascending, distinct values), target: integer
• Output: integer, the index of target, or -1

Examples

1. nums = [4,5,6,7,0,1,2], target = 0 returns 4.
2. nums = [4,5,6,7,0,1,2], target = 3 returns -1 because 3 is not in the array.
3. nums = [1], target = 0 returns -1.

Constraints

• 1 <= nums.length <= 5,000
• -10,000 <= nums[i] <= 10,000
• All values of nums are unique.
• nums is an ascending array possibly rotated at an unknown pivot.

Follow-up How would your approach change if duplicate values were allowed, and why can that force worst-case O(n)?