Suppose an array of length n sorted in ascending order is rotated between 1 and n times. Given a target value target, write a function to search for the target in the rotated sorted array.

Function Signature:

from typing import List

def search_rotated_array(nums: List[int], target: int) -> int:
    """
    Search for the target value in a rotated sorted array.

    Parameters:
    - nums: A rotated sorted array.
    - target: The target value to search for.

    Returns:
    - int: The index of the target if found, otherwise -1.
    """
    # Your code here

Example:

# Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
# Output: 4
# Explanation: The target 0 is found at index 4 in the rotated sorted array.

# Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
# Output: -1
# Explanation: The target 3 is not found in the rotated sorted array.

Note:

  • You may assume that duplicates do not exist in the array.
  • If possible, your solution should have a time complexity of O(log(n)).

Instructions:

  • Write the search_rotated_array function to solve the problem.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊