Search a Rotated Sorted List

A list of different whole numbers was sorted in ascending order and then rotated: it was cut in two and the back part was moved to the front. For example, [1, 2, 4, 6, 8, 9] cut after the 4 becomes [6, 8, 9, 1, 2, 4]. The cut can be anywhere, and the list may not have been rotated at all.

Write search_rotated(nums, target) that returns the index of target in nums, or -1 if it is not there. Aim for about as few steps as binary search takes on a sorted list, rather than checking the items one by one.

Examples

search_rotated([6, 8, 9, 1, 2, 4], 2)   # returns 4
search_rotated([6, 8, 9, 1, 2, 4], 8)   # returns 1
search_rotated([6, 8, 9, 1, 2, 4], 5)   # returns -1
search_rotated([1, 2, 4, 6], 6)         # returns 3

The last list was never rotated, and your function has to handle that too.

Constraints

• 0 <= len(nums) <= 100,000
• -10^9 <= nums[i], target <= 10^9
• All numbers in nums are different