33. Search in Rotated Sorted Array#

Difficulty: Medium

Link to Problem: To see the Search in Rotated Sorted Array problem on LeetCode, click here!

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.

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\)

def search(nums, target):
    left, right = 0, len(nums) - 1

    # Find the pivot index using binary search
    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid

    pivot = left
    left, right = 0, len(nums) - 1

    # Determine which part of the array to search in
    if target >= nums[pivot] and target <= nums[right]:
        left = pivot
    else:
        right = pivot

    # Perform binary search to find the target
    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Explanation:#

  1. The search function takes two arguments: nums, which is the rotated sorted array, and target, which is the value we want to find in the array.

  2. We initialize two pointers, left and right, which represent the range in which we are going to perform binary search. Initially, left is set to 0, and right is set to the index of the last element in the array (len(nums) - 1).

  3. We start by finding the pivot index using binary search. The pivot index is the index at which the array is rotated. We use a while loop to continue the search until left is less than right.

  4. Inside the loop, we calculate the middle index mid using integer division. We then compare the value at mid with the value at right. If nums[mid] is greater than nums[right], it means the pivot point lies to the right of mid, so we update left to mid + 1. Otherwise, the pivot point lies to the left of mid, so we update right to mid. This process continues until we find the pivot index.

  5. After finding the pivot index, we have divided the array into two parts: one part is sorted in ascending order, and the other part is also sorted in ascending order but rotated. We need to determine which part of the array contains the target value.

  6. We reset left and right pointers. If the target value is within the range [nums[pivot], nums[right]], we set left to pivot (the start of the rotated part), indicating that we should search in the rotated part. Otherwise, we set right to pivot (the end of the sorted part), indicating that we should search in the sorted part.

  7. We then perform binary search again within the chosen range (left to right) to find the target element. The binary search continues until left is less than or equal to right.

  8. Inside the binary search loop, we calculate the middle index mid and compare nums[mid] with the target value. If they are equal, we return mid as the index of the target element. If nums[mid] is less than the target, we update left to mid + 1 to search in the right half. If nums[mid] is greater than the target, we update right to mid - 1 to search in the left half.

  9. If we exit the binary search loop without finding the target, we return -1 to indicate that the target is not present in the array.

Test cases#

nums1 = [4, 5, 6, 7, 0, 1, 2]
target1 = 0
result1 = search(nums1, target1)
print(result1) 

4

# Example 2:
nums2 = [4, 5, 6, 7, 0, 1, 2]
target2 = 3
result2 = search(nums2, target2)
print(result2) 

-1

# Example 3:
nums3 = [1]
target3 = 0
result3 = search(nums3, target3)
print(result3) 

-1

Let’s analyze the time and space complexity of the provided code:

Time Complexity:

  1. Finding the pivot index using binary search takes \(O(log\ n)\) time, where ‘\(n\)’ is the number of elements in the array.

  2. After finding the pivot index, performing binary search to find the target element also takes \(O(log\ n)\) time in the worst case.

The dominant factor in the time complexity is the binary search, and since we perform two binary searches sequentially, the overall time complexity of the code is \(O(log\ n)\).

Space Complexity:

The space complexity of the code is very minimal:

  1. We use a constant amount of additional space for variables such as left, right, pivot, and mid. These variables do not depend on the input size, so they contribute \(O(1)\) space complexity.

  2. The function does not use any additional data structures that scale with the input size.

Therefore, the space complexity of the code is \(O(1)\), which means it has a constant space complexity and does not depend on the size of the input array.

In summary:

  • Time Complexity: \(O(log\ n)\)

  • Space Complexity: \(O(1)\)

Challenging Exercises:#

  1. Find Minimum Element in Rotated Sorted Array: Write an algorithm to find the minimum element in a rotated sorted array. This is a variation of the problem where you don’t need to search for a target value but instead find the smallest element.

  2. Search in a Circularly Sorted Array: Consider an array that is sorted in a circular manner (e.g., [4, 5, 6, 7, 0, 1, 2, 3]). Adapt the search algorithm to work for circularly sorted arrays while maintaining \(O(log\ n)\) complexity.