Search a rotated sorted list
Start with different integers in order from smallest to largest. Cut the list into two pieces and swap the pieces: that is a rotated list. For example, [1, 2, 4, 6, 7, 9] cut before the 6 becomes [6, 7, 9, 1, 2, 4]. The cut may also be at the very start, which leaves the list in order.
You get the rotated list nums and a number target. Find target and return its index; when it does not appear, return -1. Each call must take O(log n) time, where n is the length of the list and log n is how many times n can be halved before it reaches 1. A scan of the whole list is too slow.
nums = [6, 7, 9, 1, 2, 4], target = 2Output42 is in the second piece, at index 4.
nums = [6, 7, 9, 1, 2, 4], target = 8Output-18 is not in the list.
nums = [1, 3, 5], target = 5Output2A cut at the start leaves the list sorted, and 5 is at index 2.
1 ≤ len(nums) ≤ 105
-109 ≤ nums[i], target ≤ 109
All numbers in
numsare different.numsis a sorted list rotated at some position, possibly 0.Each call: O(log n) time.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.