Search in Rotated Sorted Array

Difficulty: Medium

Problem

There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k. For example, [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]. Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not. You must write an algorithm with O(log n) runtime complexity.

Example

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Explanation: 0 is at index 4 in the rotated array.

Brute-force approach

Scan the entire array linearly to find the target.

Steps

  1. For each index i from 0 to n-1:
  2. If nums[i] == target, return i
  3. Return -1

Time complexity: O(n) · Space complexity: O(1)

Trade-offs

  • Doesn't use the rotated-sorted structure at all
  • O(n) instead of O(log n)
  • Wastes the near-sorted property of the array

Optimal approach

Key insight: In a rotated sorted array, at least one half (left or right of mid) is always fully sorted. Check if the target lies in the sorted half's range. If yes, search there. If no, search the other half.

Modified binary search: at each step, determine which half is sorted, then check if the target falls within that sorted range to decide which half to search.

Steps

  1. Set left = 0, right = n - 1
  2. While left <= right:
  3. mid = (left + right) / 2. If nums[mid] == target, return mid
  4. If nums[left] <= nums[mid] (left half sorted):
  5. If target in [nums[left], nums[mid]): right = mid - 1
  6. Else: left = mid + 1
  7. Else (right half sorted):
  8. If target in (nums[mid], nums[right]]: left = mid + 1
  9. Else: right = mid - 1
  10. Return -1

Time complexity: O(log n) · Space complexity: O(1)