Search in Rotated Sorted Array

Problem Statement

You are given an integer array nums sorted in ascending order (with distinct values), which may be rotated at an unknown pivot index k (1 <= k < nums.length).

Example of rotation: [0,1,2,4,5,6,7] rotated by 3 - [4,5,6,7,0,1,2].
Given a target value, return the index of the target in nums, or -1 if it’s not present.

You must achieve O(log n) runtime complexity.

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

Constraints:

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

Approach: Modify the Binary Search

Since the array is rotated but sorted, a modified binary search works efficiently:

Start with low = 0 and high = len(nums) - 1.
While low <= high:
Calculate mid = low + (high - low) // 2.
If nums[mid] == target, return mid.
Determine which side is sorted:
If nums[low] <= nums[mid], the left side is sorted.
If target lies within [nums[low], nums[mid]], search left (high = mid - 1), else search right.
Else, the right side is sorted.
If target lies within [nums[mid], nums[high]], search right (low = mid + 1), else search left.

Python code

from typing import List

class Solution:
def search(self, nums: List[int], target: int) -> int:
low, high = 0, len(nums) - 1

    while low <= high:
        mid = low + (high - low) // 2

        if nums[mid] == target:
            return mid

        # Left half is sorted
        if nums[low] <= nums[mid]:
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1

    return -1

Working:

Each iteration eliminates half of the search space by checking which half is sorted.
Then we determine if the target lies in the sorted half.
If yes, we search that half; otherwise, we search the other half.