Search in Rotated Sorted Array

Problem Description

Welcome to another fun coding challenge! Today, we'll be tackling the Search in Rotated Sorted Array problem.

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 0 times.

Given the sorted rotated array nums, and a target value target, return the index of the target element. If the target element does not exist in the array, return -1.

That's it! Now, let's dive into the solution.

Solution

We can use a modified binary search approach to solve this problem. Since the array is sorted in ascending order and rotated, we cannot simply compare the middle element of the array with the target value to determine which half of the array to focus on. Instead, we'll compare the middle element of the array with the first and last elements to determine which half of the array to focus on, just like in the Find Minimum in Rotated Sorted Array problem.

Once we determine which half of the array to focus on, we can use a regular binary search to search for the target value.

Here's the Python code for our solution:

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
            elif nums[mid] >= nums[left]:
                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

Let's go through this code step-by-step.

We initialize two pointers left and right to the beginning and end of the array, respectively.

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

We use a while loop to repeatedly divide the array in half and narrow down the search space.

while left <= right:

Note that we're using left <= right instead of left < right to handle edge cases where the search space consists of a single element.

We calculate the middle index of the current search space.

mid = (left + right) // 2

If the middle element of the array is equal to the target value, then we've found the target and we can return its index.

if nums[mid] == target:
    return mid

If the middle element of the array is greater than or equal to the first element of the array, then the minimum element must be in the second half of the array, so we'll focus on the second half of the array.

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

If nums[left] <= target < nums[mid], then we know that the target must be in the first half of the array, so we set right = mid - 1. Otherwise, we know that the target must be in the second half of the array, so we set left = mid + 1.

If the middle element of the array is less than the first element of the array, then the minimum element must be in the first half of the array, so we'll focus on the first half of the array.

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

If nums[mid] < target <= nums[right], then we know that the target must be in the second half of the array, so we set left = mid + 1. Otherwise, we know that the target must be in the first half of the array, so we set right = mid - 1.

If we cannot find the target value in the array, we return -1.

return -1

Complexity Analysis

Now that we have our solution, let's analyze its time and space complexity.

Time Complexity

Our solution uses a modified binary search to search for the target value in the rotated sorted array. Since we're dividing the search space in half at each step, the time complexity of our solution is O(log n), where n is the length of the input array.

Space Complexity

Our solution uses a constant amount of extra space to keep track of the pointers left, right, and mid. Therefore, the space complexity of our solution is O(1).

Conclusion

And there you have it! We've successfully tackled the Search in Rotated Sorted Array problem. I hope you found this blog post helpful and informative. Happy Coding! 😎

Eyuel's Blog⭐⭐⭐