Search in Rotated Sorted Array

Naive Solution

The most straightforward solution is to iterate through the array nums and check if each element is equal to the target. If we find the target, we return its index. If we reach the end of the array without finding the target, we return -1.

Code (Python)

def search_naive(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

Time Complexity

The time complexity of this naive solution is O(n), where n is the length of the array nums, because, in the worst case, we have to iterate through the entire array.

Space Complexity

The space complexity is O(1) because we are only using a constant amount of extra space.

Optimal Solution

Since the array is sorted (and rotated), we can use a modified binary search to find the target in O(log n) time. The idea is to first find the pivot (the index of the smallest element in the array), and then perform binary search in the appropriate half of the array.

Algorithm

1. Find the Pivot: Use binary search to find the index of the smallest element in the array. This is the point where the array is rotated.
2. Binary Search:
   • If the target is equal to the element at the pivot, return the pivot index.
   • If the target is greater than or equal to the first element of the array, search in the first half of the array (from index 0 to pivot - 1).
   • Otherwise, search in the second half of the array (from index pivot to the end of the array).

Code (Python)

def search(nums, target):
    if not nums:
        return -1

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

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid

        # Check if the left side is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Otherwise, the right side is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

Time Complexity

The time complexity of the optimal solution is O(log n), where n is the length of the array nums. This is because we are using binary search to find both the pivot and the target.

Space Complexity

The space complexity is O(1) because we are only using a constant amount of extra space.

Edge Cases

• Empty Array: If the input array nums is empty, return -1.
• Single Element Array: If the array contains only one element, check if that element is equal to the target. If it is, return 0; otherwise, return -1.
• Target Not Found: If the target is not in the array, return -1.
• Array Not Rotated: If the array is not rotated (i.e., it is sorted in ascending order), the pivot will be 0. The algorithm should still work correctly in this case.