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.

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0  → 4
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3  → -1
Input: nums = [1], target = 0                    → -1

Solution

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=0 in [4,5,6,7,0,1,2]: mid=3 (7), left half [4..7] sorted but 0 not in [4,7), go right; mid=5 (1), left half [0,1) of this window sorted, 0 in [0,1), go left; mid=4 (0), match at index 4.

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.