Solution Explanation: Search in Rotated Sorted Array

This problem requires finding the index of a target element within a rotated sorted array. A rotated sorted array is a sorted array that has been rotated at some pivot point. For example, [0, 1, 2, 4, 5, 6, 7] rotated at pivot 3 becomes [4, 5, 6, 7, 0, 1, 2]. The challenge is to solve this efficiently, in O(log n) time complexity, which suggests a binary search approach.

Approach: Modified Binary Search

A standard binary search won't work directly because the array isn't sorted globally. However, we can exploit the fact that at least one half of the array will always be sorted. This is the key insight that allows us to adapt the binary search algorithm.

The algorithm works as follows:

1. Initialization: Set left to 0 and right to nums.length - 1.

2. Iteration: While left is less than right:

   • Calculate the mid index.
   • Check if the left half is sorted: If nums[left] <= nums[mid]:
     • If the target falls within the range of the sorted left half (nums[left] <= target <= nums[mid]), then search in the left half (right = mid).
     • Otherwise, search in the right half (left = mid + 1).
   • Otherwise (right half is sorted):
     • If the target falls within the range of the sorted right half (nums[mid] < target <= nums[right]), then search in the right half (left = mid + 1).
     • Otherwise, search in the left half (right = mid).

3. Termination: The loop terminates when left and right converge. At this point:

   • If nums[left] equals the target, return left.
   • Otherwise, the target isn't present, so return -1.

Time and Space Complexity

• Time Complexity: O(log n). The binary search algorithm halves the search space in each iteration, resulting in logarithmic time complexity.

• Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code Examples (Python and Java)

The core logic remains consistent across different programming languages. Here are examples in Python and Java to illustrate:

Python:

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
            # Check if left half is sorted
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            # Otherwise, right half is sorted
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1  # Target not found
 

Java:

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            // Check if left half is sorted
            if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else { // Right half is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1; // Target not found
    }
}

The other language examples provided in the original response follow a very similar structure, adapting the core binary search logic to handle the rotated array. The key differences are primarily in syntax and data structure handling specific to each language.