Leetcode - 33. Search in Rotated Sorted Array

Medium

Dec 22, 2025

#binary-search

33. Search in Rotated Sorted Array

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

Prior to being passed to your function, nums is possibly left rotated at an unknown 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 left rotated by 3 indices 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.

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

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

Constraints:

Notes

Intuition

First find where the array was rotated (the pivot/minimum element), which splits the array into two sorted subarrays. Then determine which subarray contains the target and perform a standard binary search on it.

Implementation

First, binary search to find the pivot index using the "minimum in rotated sorted array" approach (where both neighbors are larger, or we're at a boundary). Then check if the target falls in the range from index 0 to pivot-1 (the "left" sorted portion) or from pivot to end (the "right" sorted portion). Binary search the appropriate half.

Edge-cases

When determining which half to search, check if target falls within nums[0] to nums[pivot-1]. Handle the case where pivot is 0 (array wasn't rotated or rotated n times).

Time: O(log n) — two binary searches
Space: O(1) — only tracking pointers

Complexity

Solution

from typing import List

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        # Find pivot index (min in rotated sorted)
        l, r = 0, n - 1

        pivot = -1
        while l <= r:
            m = (l + r) // 2
            if (m == 0 or nums[m - 1] > nums[m]) and (m == n - 1 or nums[m + 1] > nums[m]):
                pivot = m
                break
            elif nums[r] < nums[m]:
                l = m + 1
            else:
                r = m - 1

        if pivot == -1:
            raise RuntimeError("pivot index not found, check your implementation")

        # Search in correct side of array
        l, r = 0, n - 1
        if target >= nums[0] and pivot != 0 and target <= nums[pivot - 1]:
            # search from 0 to pivot
            r = pivot - 1
        else:
            # search from pivot to end
            l = pivot
            pass

        while l <= r:
            m = (l + r) // 2
            if nums[m] == target:
                return m
            elif nums[m] < target:
                l = m + 1
            else:
                r = m - 1
        
        return -1
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()