A list of different integers was sorted in increasing order and then rotated by some amount
(possibly none): some items were moved, in order, from the end to the front, the way
[2, 5, 8, 9, 13] can become [9, 13, 2, 5, 8].
Given the rotated list nums and an integer target, return the index of target in nums, or
-1 if it isn't there. Your solution should take O(log n) time.
Example 1
- Input
- nums = [9, 13, 2, 5, 8], target = 5
- Output
- 3
Example 2
- Input
- nums = [9, 13, 2, 5, 8], target = 10
- Output
- -1
Constraints
numsholds 1 to 5000 numbers, all different.- Every number, and
target, is between −10⁴ and 10⁴. numsis an increasing list rotated by some amount from 0 to n − 1.
Show the pattern
Binary search
However the list was rotated, at least one of the two halves around the middle is in order, and you can tell which. Checking whether the target fits in that half tells you which half to keep.
See binary search in a visualiserShow the approach
Binary search, with one extra question at each step. Keep [lo, hi] and look at mid; if
nums[mid] is the target, you're done. Otherwise one of the two halves is in order:
- If
nums[lo] ≤ nums[mid], the left half is in order. Ifnums[lo] ≤ target < nums[mid], the target can only be there:hi = mid − 1. Otherwiselo = mid + 1. - Otherwise the right half is in order. If
nums[mid] < target ≤ nums[hi], search it:lo = mid + 1. Otherwisehi = mid − 1.
When the range runs out, the target isn't in the list.
Time: O(log n) · Space: O(1)