We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Search in Rotated Sorted Array

Difficulty: Medium

Problem Description

Given an integer array nums sorted in ascending order and possibly rotated at an unknown pivot, return the index of a target if it exists in nums, or -1 if it does not.

Key Insights

  • The array is sorted but rotated, which means it has two sorted subarrays.
  • A modified binary search can be employed to find the target efficiently.
  • The middle element can help determine which subarray to search next based on its value relative to the target and the endpoints of the current search range.

Space and Time Complexity

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

Solution

The algorithm uses a binary search approach, adapted for the rotated sorted array. We keep track of two pointers, left and right, that represent the current search range. We continually calculate the midpoint to divide the search space in half. Depending on the value of the midpoint and the target compared to the endpoints of the current range, we can decide whether to search the left half or the right half of the current array.

Code Solutions

def search(nums, target):
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if nums[mid] == target:
            return mid
        
        # Determine if the left half is sorted
        if nums[left] <= nums[mid]:
            # Target is in the left half
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # Target is in the right half
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
                
    return -1
← Back to All Questions