Find in a Rotated List
nums holds distinct numbers that were sorted in increasing order and then rotated: some items from the front were moved to the back in the same order, possibly none of them. So [4, 7, 9, 1, 2] came from [1, 2, 4, 7, 9].
Return the index of target in nums, or -1 if it is not there. An empty list gives -1. Aim for logarithmic time: one half of any range is always in sorted order, which tells you which half can hold the target.
Example 1
nums [4,7,9,1,2]
target 1
returns 3
1 sits at index 3.
Example 2
nums [4,7,9,1,2]
target 5
returns -1
5 is not in the list.
Constraints
0 <= len(nums) <= 100-1000 <= nums[i], target <= 1000- All values of
numsare distinct
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Sorting and searching problems
- H-IndexMedium
- K Closest ValuesMedium
- Kth Smallest Pair SumMedium
- Least Truck CapacityMedium
- Merge IntervalsMedium
- Rebuild the LineMedium
- Smallest Divisor Under a LimitMedium
- Spread the TentsMedium