Find a Target's Index in a Rotated Sorted Array of Distinct Integers

An array of distinct integers was sorted in strictly increasing order and then rotated at an unknown pivot: for some k with 0 <= k < n, the array [a0, a1, ..., a(n-1)] became [ak, a(k+1), ..., a(n-1), a0, a1, ..., a(k-1)]. A rotation with k = 0 leaves the array unchanged.

Given the rotated array nums and an integer target, return the index of target in nums, or -1 if it is not present. The interviewer expects a solution whose running time is logarithmic in the length of the array.

Function Signature

def search_rotated(nums: list[int], target: int) -> int:

Rules

• Indices are 0-based.
• All values in nums are distinct, so the answer is unique.
• nums is guaranteed to be a rotation of a strictly increasing array.

Constraints

• 1 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

Examples

Example 1

• Input: nums = [15, 18, 22, 3, 7, 11], target = 7
• Output: 4
• Explanation: the array is [3, 7, 11, 15, 18, 22] rotated by three positions, and 7 sits at index 4.

Example 2

• Input: nums = [15, 18, 22, 3, 7, 11], target = 20
• Output: -1

Example 3

• Input: nums = [1, 4, 9, 12], target = 12
• Output: 3
• Explanation: this array was not rotated (k = 0).