#33 Search in Rotated Sorted Array
Start with an ascending array of distinct integers, then rotate it at some
unknown pivot. The tail gets moved to the front. So a sorted
[0,1,2,4,5,6,7] might arrive as [4,5,6,7,0,1,2].
Given the rotated array nums and a target, return the index of
target, or -1 if it's absent. Required complexity: O(log n), so
scanning is out.
Examples
nums = [4, 5, 6, 7, 0, 1, 2], target = 04The array was rotated at index 4; the target sits there.
nums = [4, 5, 6, 7, 0, 1, 2], target = 3-13 isn't in the array.
nums = [1], target = 10A rotation by 0 (or by n) leaves the array as-is, your code must handle the unrotated case too.
Constraints
1 ≤ nums.length ≤ 5000-10⁴ ≤ nums[i], target ≤ 10⁴All values are distinctnums was ascending before being rotated at some pivot (possibly 0)
The explainer is the good part.
Sign in for the full intuition build-up, every approach from naive to optimal with complexity analysis, progressive hints, and commented solutions in Python, JavaScript, and Java. All free.
Want a taste first? Try a free sample: Two Sum or Valid Parentheses.