LeetCode #33 - Search in Rotated Sorted Array

You are given an integer array nums sorted in ascending order, which is then rotated at an unknown pivot index. You are also given an integer target. If the target exists in the array, return its index. Otherwise, return -1. Your solution should be in O(log n) time complexity.
Function Signature: def search(nums: List[int], target: int) -> int:
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Explanation: The target value is located at index 4.
Example 2:
Input: nums = [1], target = 0
Output: -1
Explanation: The target value does not exist in the input array.
Constraints: 1 <= nums.length <= 5000; -10^4 <= nums[i] <= 10^4; All integers in nums are unique; nums is an ascending array that is then rotated.