Skip to content

Leetcode 33 - Search in Rotated Sorted Array

Difficulty: medium

Table of contents

Open Table of contents


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.

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



Given a sorted and rotated array, the goal is to find the index of a target value efficiently (with O(log n) time complexity). To achieve logarithmic time complexity, we can use a modified version of binary search.

The primary challenge here is dealing with the rotation in the array. First, identify whether the target value resides in the rotated part or the sorted part of the array. Then proceed with binary search in the identified subarray.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # Define the start and end pointers
        start = 0
        end = len(nums) - 1

        # Continue the search while start is less than or equal to end
        while start <= end:
            mid = start + (end - start) // 2  # Find the middle element

            # If target is found, return its index
            if nums[mid] == target:
                return mid

            # Determine if left half is sorted
            if nums[start] <= nums[mid]:
                # If target is in the sorted left half, update end pointer
                if nums[start] <= target <= nums[mid]:
                    end = mid - 1
                # Otherwise, update start pointer
                    start = mid + 1
            # If right half is sorted
                # If target is in the sorted right half, update start pointer
                if nums[mid] <= target <= nums[end]:
                    start = mid + 1
                # Otherwise, update end pointer
                    end = mid - 1

        # If target is not found, return -1
        return -1


Time and Memory Complexity