LeetCode 033 - Search in Rotated Sorted Array

2026-07-07

medium　array　binary search

If you're not familiar with binary search, check out LeetCode 704 - Binary Search first.

For the rotation mechanics, LeetCode 153 - Find Minimum in Rotated Sorted Array is a good warm-up.

You are given an array of length n which was originally sorted in ascending order. It has been rotated between 1 and n times.

For example, [1,2,3,4,5,6] might become:

• [3,4,5,6,1,2] if rotated 4 times.
• [1,2,3,4,5,6] if rotated 6 times (back to original).

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

All elements are unique. Can you solve it in O(log N) time?

Example 1:

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

Output: 4

Example 2:

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

Output: -1

Constraints:

• 1 <= nums.length <= 1,000
• -1,000 <= nums[i], target <= 1,000
• All values of nums are unique.

Solution 1:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # Approach: Single-Pass Binary Search — Identify the Sorted Half
        # At every midpoint, exactly one of the two halves is guaranteed to be sorted.
        # Compare nums[mid] against nums[r_idx] to determine which half it is:
        #
        # Case A — nums[mid] <= nums[r_idx]: the RIGHT half is sorted.
        #   - If target falls within (nums[mid], nums[r_idx]], search right: l_idx = mid + 1.
        #   - Otherwise the target is in the left half: r_idx = mid - 1.
        #
        # Case B — nums[mid] > nums[r_idx]: the LEFT half is sorted.
        #   - If target falls within [nums[l_idx], nums[mid]), search left: r_idx = mid - 1.
        #   - Otherwise the target is in the right half: l_idx = mid + 1.
        #
        # Return mid immediately if nums[mid] == target.
        # Return -1 if pointers cross without a match.
        # Time Complexity: O(log N).
        # Space Complexity: O(1).
        l_idx, r_idx = 0, len(nums) - 1
        while l_idx <= r_idx:
            mid = (l_idx + r_idx) // 2
            if nums[mid] == target:
                return mid

            if nums[mid] <= nums[r_idx]:
                if nums[mid] < target <= nums[r_idx]:
                    l_idx = mid + 1
                else:
                    r_idx = mid - 1
            else:
                if nums[l_idx] <= target < nums[mid]:
                    r_idx = mid - 1
                else:
                    l_idx = mid + 1
        return -1

Solution 2:

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        # Approach: Find Pivot First, Then Standard Binary Search
        # 1. Use a binary search to locate the pivot — the index of the minimum element
        #    (same technique as LeetCode 153). The pivot is where the rotation begins.
        # 2. Use the pivot to decide which contiguous sorted half to search:
        #    - If target falls in [nums[pivot], nums[-1]], search the right segment.
        #    - Otherwise search the left segment [nums[0], nums[pivot-1]].
        # 3. Run a standard binary search on the chosen segment.
        # Two separate O(log N) passes, still O(log N) overall.
        # Time Complexity: O(log N).
        # Space Complexity: O(1).
        l_idx, r_idx = 0, len(nums) - 1
        while l_idx < r_idx:
            mid = (l_idx + r_idx) // 2
            if nums[r_idx] < nums[mid]:
                l_idx = mid + 1
            else:
                r_idx = mid

        pivot = l_idx

        l_idx, r_idx = 0, len(nums) - 1
        if pivot > 0:
            if nums[pivot] <= target <= nums[r_idx]:
                l_idx = pivot
            else:
                r_idx = pivot - 1

        while l_idx <= r_idx:
            mid = (l_idx + r_idx) // 2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                l_idx = mid + 1
            else:
                r_idx = mid - 1
        return -1

Conclusion

Today we searched a rotated sorted array in O(log N) two ways.

The core challenge: a rotated array isn't fully sorted, so we can't just binary search it directly. But at any midpoint, one of the two halves is always guaranteed to be contiguously sorted. Solution 1 exploits this — it identifies the sorted half first, checks whether the target falls inside it, and searches accordingly. One pass, clean and direct.

Solution 2 breaks the problem into two familiar pieces: first find the pivot (the minimum element, using the same technique as LeetCode 153), then use the pivot to pick which sorted half to run a standard binary search on. Slightly more code, but easier to reason about because each step is a well-known pattern.

Both solutions run in O(log N). The single-pass approach in Solution 1 is generally preferred in interviews for its compactness. The pivot-first approach in Solution 2 is more modular and shows how to reuse existing building blocks.