Problem

You are given a sorted integer array nums with distinct values that has been possibly rotated at an unknown pivot index k (where 1 <= k < nums.length). The rotated array looks like this: [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed).

For example, the array [0, 1, 2, 4, 5, 6, 7] might be rotated at pivot index 3 to become [4, 5, 6, 7, 0, 1, 2].

Given the rotated array nums and an integer target, your task is to return the index of target if it is found in nums, or -1 if it is not present.

Important Requirement: Your solution must have a runtime complexity of O(log n).

Examples

1. Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4
2. Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1
3. Input: nums = [1], target = 0 Output: -1

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

## Optimal Solution: Binary Search

This problem can be solved efficiently using a modified binary search algorithm. The key idea is to adapt the binary search to handle the rotated nature of the array.

```python
def search_rotated_array(nums, target):
    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

Explanation:

1. Initialization: Initialize left to 0 and right to the last index of the array.
2. Binary Search Loop: Continue the loop as long as left is less than or equal to right.
3. Calculate Midpoint: Find the middle index mid.
4. Target Found: If nums[mid] equals the target, return mid.
5. Check Sorted Side: Determine if the left half of the array (from nums[left] to nums[mid]) is sorted.
   • If the left side is sorted, check if the target lies within this sorted range. If it does, update right to mid - 1; otherwise, update left to mid + 1.
6. Right Side Sorted: If the left side is not sorted, then the right side must be sorted. Check if the target lies within this sorted range. If it does, update left to mid + 1; otherwise, update right to mid - 1.
7. Target Not Found: If the loop finishes without finding the target, return -1.

Example:

nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
print(search_rotated_array(nums, target))  # Output: 4

Big(O) Runtime Analysis

The algorithm uses binary search, which divides the search space in half with each iteration. Therefore, the time complexity is O(log n), where n is the number of elements in the array.

Big(O) Space Usage Analysis

The algorithm uses a constant amount of extra space for variables like left, right, and mid. Thus, the space complexity is O(1).

Edge Cases

1. Empty Array: If the input array nums is empty, the algorithm should return -1.
2. Single Element Array: If the array contains only one element, the algorithm should check if that element is equal to the target and return the appropriate index or -1.
3. Target at the Beginning or End: The algorithm should correctly handle cases where the target is at the beginning or end of the array.
4. Array Not Rotated: If the array is not rotated (i.e., it is sorted in ascending order), the algorithm should still work correctly.
5. Duplicate Values: Although the problem states that the values are distinct, handling duplicate values would require additional checks to determine the sorted side, which could affect the runtime complexity in the worst case.