LeetCode Solutions Blog

Search in Rotated Sorted Array

Number: 33

Difficulty: Medium

Paid? No

Problem Description

Given a rotated sorted array with distinct integers, determine the index of a target integer. The rotated array is formed by taking an originally sorted array and rotating it at an unknown pivot. Return the index of the target if found, or -1 if not found. The solution must run in O(log n) time.

Key Insights

The array is originally sorted and then rotated at an unknown pivot.
Use a modified binary search to accommodate the rotation.
At every step, determine which half of the array is properly sorted.
Narrow down the search based on the sorted half and the target’s value.

Space and Time Complexity

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

Solution

We perform a binary search while accounting for the possibility that the array is rotated. At each iteration, we check if the left-to-mid portion is sorted. If it is, and the target falls within that range, we search the left half; otherwise, we search the right half. If the left half is not sorted, then the right half must be sorted, and similarly, we check if the target is in that sorted half. This approach ensures logarithmic time complexity while handling the rotation correctly.

Code Solutions

# Define a function to search for the target in a rotated sorted array.
def search(nums, target):
    # Initialize pointers for binary search.
    left, right = 0, len(nums) - 1

    # Loop until the search space is exhausted.
    while left <= right:
        # Compute the middle index.
        mid = (left + right) // 2
        
        # If the mid element is the target, return its index.
        if nums[mid] == target:
            return mid
        
        # Check if the left part of the array is sorted.
        if nums[left] <= nums[mid]:
            # If the target is within the sorted left half, adjust the right pointer.
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                # Otherwise, search the right half.
                left = mid + 1
        else:
            # The right half must be sorted.
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
                
    # If the target is not found, return -1.
    return -1

# Example usage:
# result = search([4,5,6,7,0,1,2], 0)
# print(result)  # Expected output: 4