33. Search in Rotated Sorted Array

Summary

Given a rotated sorted array nums, return the index of target if it exists, otherwise -1. The solution must run in O(log N) time, so binary search is required.

Approach

Perform a modified binary search that exploits the fact that at least one side of the pivot is still sorted.

Example: nums = [4,5,6,7,0,1,2], target = 0 mid might land on 7. The left half [4,5,6,7] is sorted and the target is not inside it, so we search the right half instead.

To avoid mistakes, always determine which half is sorted and whether the target falls inside that half:

If nums[left] <= nums[mid], the left half is sorted. Search it when nums[left] <= target < nums[mid]; otherwise search the right half.
Otherwise the right half is sorted, so search it when nums[mid] < target <= nums[right]; otherwise search the left half.

Functionality

Initialization:

left = 0
right = 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.

Complexity

Time Complexity: O(log N) because the search space halves each iteration. Space Complexity: O(1).