Search in Rotated Sorted Array

Problem

Time-series databases often store ring-buffer segments that are sorted within a window but rotated when the ring wraps. Given a sorted integer array that was rotated at an unknown pivot (all values are distinct), search for a target and return its index or -1 if not found.

Example 1:

Input: nums = [9, 12, 15, 20, 3, 6], target = 6
Output: 5

Example 2:

Input: nums = [9, 12, 15, 20, 3, 6], target = 7
Output: -1

Example 3:

Input: nums = [4], target = 0
Output: -1

Constraints:

• 1 <= nums.length <= 5000
• -10^4 <= nums[i], target <= 10^4
• All values of nums are unique.
• nums was sorted in ascending order and then rotated between 1 and n times.
• The time complexity must be O(log n).

Solution Breakdown

Approach - exact-match binary search adapted to a rotated array by first finding the sorted half.

In a rotated array you cannot decide direction from nums[mid] versus target alone, because the array is not globally ordered. The structural fact that rescues you: a single rotation splits the array into two ascending segments, so whichever side mid lands in, at least one half - left or right of mid - is fully sorted. Each step, after checking nums[mid] == target for an early return, you identify the sorted half with one comparison. If nums[low] <= nums[mid] the left half is sorted; then if nums[low] <= target < nums[mid] the target lies inside that ordered range so you search left (high = mid - 1), otherwise search right (low = mid + 1). If instead nums[low] > nums[mid] the right half is sorted; if nums[mid] < target <= nums[high] the target is in that ordered range so search right, otherwise search left. Because you only ever test the target against a genuinely sorted half, the range check is reliable, and each step discards half the window just like plain binary search. Loop on low <= high and return -1 when it exits. Trace target=6 in [9,12,15,20,3,6]: mid=2 (15), left half [9..15] sorted but 6 not in [9,15), go right; mid=4 (3), left half [3,3) of this window sorted, 6 not in it, go right; mid=5 (6), match at index 5.

Edge cases - a single-element array resolves in one comparison (found or -1); an unrotated array always reads the left half as sorted and behaves like ordinary binary search; the inclusive vs exclusive bounds in the two range checks (<= on the boundary you came from, < on mid) are what keep duplicates of the endpoints from misrouting. Assumes distinct values.

Complexity - O(log n) time, O(1) space - one half is eliminated per iteration using only pointers.