Search in Rotated Sorted Array

You are given an array of length n which was originally sorted in ascending order. It has now been rotated between 1 and n times. For example, the array nums = [1,2,3,4,5,6] might become:

• [3,4,5,6,1,2] if it was rotated 4 times.
• [1,2,3,4,5,6] if it was rotated 6 times.

Given the rotated sorted array nums and an integer target, return the index of target within nums, or -1 if it is not present.

You may assume all elements in the sorted rotated array nums are unique,

A solution that runs in O(n) time is trivial, can you write an algorithm that runs in O(log n) time?

Approach

Perform binary search while determining which half is sorted. At each step, if the left half nums[left..mid] is sorted, check if target lies within it; otherwise search the right half. If the right half is sorted, do the symmetric check. This handles cases where the array is not rotated and when the target is missing.

Why It Works

In a rotated sorted array with unique elements, one side of mid is always sorted. The target must lie in the sorted half if it falls within its bounds; otherwise it must be in the other half. Each decision discards half the search space while preserving the target if it exists.

Complexity

• Time: O(log n)
• Space: O(1)

Reference Implementation (Python)

class Solution:
    def search(self, 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