Problem Statement

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is 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).

For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Additional information

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• All values of nums are unique.
• nums is an ascending array that is possibly rotated.
• -10^4 <= target <= 10^4

Example 1:

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0

Output: 4

Example 2:

Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 3

Output: -1

Example 3:

Input: nums = [1], target = 0

Output: -1

Brute Force

Intuition
Even though the array is rotated, we can still iterate through every element to find the target. This ignores the sorted property entirely but guarantees a correct answer.

Algorithm

1. Iterate i from 0 to len(nums) - 1.
2. If nums[i] == target, return i.
3. If the loop finishes without finding the target, return -1.

def search(nums: list[int], target: int) -> int:
    for i, n in enumerate(nums):
        if n == target:
            return i
    return -1

Time & Space Complexity

• Time complexity: O(n)

• Reason: We scan the entire array.

• Space complexity: O(1)

• Reason: Constant extra space.

Modified Binary Search (Optimal)

Intuition
A rotated sorted array is essentially two sorted subarrays concatenated together. When we split the array at any mid index, at least one half (left or right) will always be sorted.

1. If nums[l] <= nums[mid], the left half [l...mid] is sorted.
2. If nums[l] > nums[mid], the right half [mid...r] is sorted.

Once we know which half is sorted, we can check if the target lies within that sorted range. If it does, we search that half. If not, we search the other half.

Algorithm

1. Initialize l = 0 and r = len(nums) - 1.
2. While l <= r:

• Calculate mid = (l + r) // 2.

• If nums[mid] == target, return mid.

• Check if Left Half is Sorted (nums[l] <= nums[mid]):

• If nums[l] <= target < nums[mid]: Search left (r = mid - 1).

• Else: Search right (l = mid + 1).

• Else (Right Half is Sorted):

• If nums[mid] < target <= nums[r]: Search right (l = mid + 1).

• Else: Search left (r = mid - 1).

3. Return -1.

def search(nums: list[int], target: int) -> int:
    l, r = 0, len(nums) - 1
    
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return mid
        
        # Check if the left portion is sorted
        if nums[l] <= nums[mid]:
            if target > nums[mid] or target < nums[l]:
                l = mid + 1
            else:
                r = mid - 1
        # Otherwise, the right portion is sorted
        else:
            if target < nums[mid] or target > nums[r]:
                r = mid - 1
            else:
                l = mid + 1
                
    return -1

Time & Space Complexity

• Time complexity: O(log n)

• Reason: We discard half of the array in every step, just like standard binary search.

• Space complexity: O(1)

• Reason: We only use pointer variables.