Given a rotated sorted array, write a function to search for a target value. If found, return its index; otherwise, return -1. ### Function Signature ```python def search(nums: List[int], target: int) -> int: ``` ### Constraints - `1 <= nums.length <= 5000` - `-10^4 <= nums[i] <= 10^4` ### Examples 1. Input: `search([4,5,6,7,0,1,2], 0)` Output: `4` 2. Input: `search([4,5,6,7,0,1,2], 3)` Output: `-1`

``` def search(nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid if nums[left] <= nums[mid]: 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 ```