Search in Rotated Sorted Array
Part of Practice: Rotations & Partitions
A sorted array of distinct integers was rotated at some unknown position, so it looks like two ascending runs, e.g. [4,5,6,7,0,1,2]. Given this rotated array nums and a target, return the index of target, or -1 if it is absent.
Required time: O(log n). The array might also not be rotated at all, and it has at least one element.
Examples
- Input:
- nums = [4, 5, 6, 7, 0, 1, 2], target = 0
- Output:
- 4
- Input:
- nums = [4, 5, 6, 7, 0, 1, 2], target = 3
- Output:
- -1
3 is not in the array.
- Input:
- nums = [1], target = 0
- Output:
- -1
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.