Search a Rotated Sorted Array in One Binary-Search Pass

Problem Statement

You are given an integer array nums sorted in strictly ascending order with distinct values. Prior to being passed to your function, nums was possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed).

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

You must design an algorithm with O(log n) runtime complexity that operates in a single binary-search pass (without finding the pivot index first) and does not modify the input array.

Function Signature

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

Input & Output Format

• Input: A list of integers nums and an integer target.
• Output: An integer representing the 0-based index of target in nums, or -1 if target is not found.

Examples

Example 1

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Explanation: 0 is located at index 4.

Example 2

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Output: -1
Explanation: 3 is not present in nums.

Example 3

Input: nums = [1], target = 0
Output: -1
Explanation: nums contains only 1 element, which does not match target.

Constraints

• 1 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9
• All values in nums are unique.
• nums is guaranteed to be rotated at some index, or not rotated at all.
• -10^9 <= target <= 10^9

Edge Cases to Consider

• Array with only one or two elements.
• Array that was not rotated (or rotated by n steps, returning to original order).
• Target located at the extreme ends (nums[0] or nums[-1]).
• Target located immediately before or after the rotation point.