Search in Rotated Sorted Array
Search for `target` in a sorted array that has been rotated at an unknown pivot. Return the index of `target`, or -1 if not found. The solution must run in O(log n). **Core Insight:** Even after rotation, one half of the array is always sorted. At each binary search step, determine which half is sorted by comparing `nums[left]` with `nums[mid]`. Then check if `target` falls within the sorted half — if yes, search there; if no, search the other half. **Algorithm:** `left = 0`, `right = n-1`. While `left <= right`: compute `mid`. If `nums[mid] == target` return `mid`. If `nums[left] <= nums[mid]` (left half is sorted): if `nums[left] <= target < nums[mid]` search left, else search right. Else (right half is sorted): if `nums[mid] < target <= nums[right]` search right, else search left. **Key insight:** Exactly one of the two halves is always sorted after a single rotation. Identifying which one lets us make a binary decision. **Complexity:** Time O(log n). Space O(1).
Constraints
- •
1 ≤ nums.length ≤ 5000 - •
All values are unique
def search(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1