33. Search in Rotated Sorted Array
An ascending array of distinct integers was rotated at an unknown pivot: some prefix was cut off and glued onto the end. A rotation of zero is allowed, so the array might also be untouched. For example, rotating [0, 1, 2, 4, 5, 6, 7] by four gives [4, 5, 6, 7, 0, 1, 2].
Given the rotated array nums and an integer target, return the 0-based index where target sits in nums, or -1 if it does not appear.
A linear scan is easy — the real exercise is doing it in O(log n) time.
Example 1:
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Explanation: The sorted array [0..7] was rotated by four; 0 now lives at index 4.
Example 2:
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
Explanation: 3 is not anywhere in the array, so the answer is -1.
Constraints:
- 1 ≤ nums.length ≤ 5000
- -10⁴ ≤ nums[i] ≤ 10⁴
- All values of nums are distinct
- -10⁴ ≤ target ≤ 10⁴
- nums is an ascending array rotated at some pivot (possibly by 0)
Hints:
Cut a rotated array at any midpoint and at least one of the two halves is still perfectly sorted — compare nums[lo] with nums[mid] to tell which one.
Once you know which half is sorted, a simple range check (is target between its endpoints?) tells you whether to stay in that half or jump to the other. That single decision per step is a binary search.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Expected output: 4