Search in Rotated Sorted Array

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 (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and 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 in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

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

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

1 <= nums.length <= 5000
-10^4 <= nums[i] <= 10^4
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-10^4 <= target <= 10^4

Solution

Approach: Modified Binary Search

The key insight is that at least one half of the array (left or right of mid) is always sorted. We can determine which half is sorted, then check if the target is in that sorted half or the other half.

Algorithm:

Use binary search with left and right pointers
Calculate mid and check if it’s the target
Determine which half is sorted by comparing nums[left] with nums[mid]
Check if target is in the sorted half’s range
Adjust search boundaries accordingly

Implementation

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

            # Left half is sorted
            if nums[left] <= nums[mid]:
                # Target is in left sorted half
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # Right half is sorted
            else:
                # Target is in right sorted half
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

Alternative (More Explicit):

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

            # Check which half is sorted
            if nums[left] <= nums[mid]:
                # Left half is sorted [left...mid]
                if target >= nums[left] and target < nums[mid]:
                    # Target is in sorted left half
                    right = mid - 1
                else:
                    # Target is in unsorted right half
                    left = mid + 1
            else:
                # Right half is sorted [mid...right]
                if target > nums[mid] and target <= nums[right]:
                    # Target is in sorted right half
                    left = mid + 1
                else:
                    # Target is in unsorted left half
                    right = mid - 1

        return -1

Complexity Analysis

Time Complexity: O(log n), where n is the length of the array. We perform binary search.
Space Complexity: O(1), we only use a constant amount of extra space.

Key Insights

At Least One Half is Sorted: In a rotated sorted array, when we pick any middle point, at least one of the two halves [left, mid] or [mid, right] must be sorted in ascending order.
Determine Sorted Half: We check if the left half is sorted by comparing nums[left] <= nums[mid]. If true, left half is sorted; otherwise, right half is sorted.
Target in Sorted Half: Once we identify the sorted half, we can easily check if the target falls within its range using simple comparisons.
Elimination Strategy: If target is in the sorted half, search there. Otherwise, it must be in the unsorted half (which contains the rotation point).
Edge Cases: The <= in nums[left] <= nums[mid] handles the case when left == mid (array of size 1 or 2), ensuring we correctly identify the sorted portion.