Search in a rotated sorted array
DSA, Medium
Which structure or algorithm, and what does it cost.
A sorted list of distinct integers was cut at some position and the two parts were swapped, so the list now starts in the middle of the sorted order and wraps around. For example, [1, 3, 4, 6, 7, 9] can become [6, 7, 9, 1, 3, 4]. The list may also be left uncut. You get this list nums and a number target. Return the position of target in nums, or -1 if it is not there. You do not know where the cut is.
Examples
Input nums = [6, 7, 9, 1, 3, 4], target = 3
Output 4
Why 3 is at position 4. The cut is between 9 and 1.
Input nums = [6, 7, 9, 1, 3, 4], target = 5
Output -1
Why 5 is not in the list, even though it lies between 4 and 6 in sorted order.
Input nums = [8], target = 8
Output 0
Why Edge case: a list with one item. The same code must handle it with no special branch.
Constraints
- 1 <= length of nums <= 100,000.
- All values in nums are different. Each value is between -1,000,000,000 and 1,000,000,000.
- nums is a sorted list that was cut once and swapped, or not cut at all.
- The list is large and you search many times, so scanning every item is not accepted.
Your answer must contain
- The approach in words, and why it still works although the list is not fully sorted
- Code or pseudocode in any language
- Time and memory cost, with the reason for each
- A hand trace of example 1 through your code