Search in Rotated Sorted Array

PracticeNeetCode ↗LeetCode ↗

Given a rotated sorted array of unique integers and a target value, return its index, or -1 if it isn't present. The solution must run in O(log n) time.

Example

Key Pointers

• At every step, at least one half of the current range (left-to-mid or mid-to-right) is guaranteed to still be normally sorted — comparing the leftmost value to the middle value tells you which one.
• Once you know which half is sorted, a plain range check tells you whether the target could live there.
• If the target isn't in the sorted half's range, it must be in the other, still-rotated half.

Step-by-Step Analysis

1. Set left = 0, right = len(nums) - 1.
2. While left has not passed right: compute mid; if nums[mid] equals the target, return mid.
3. If nums[left] is less than or equal to nums[mid], the left half is sorted: when the target falls within that sorted range, search the left half; otherwise search the right half.
4. Otherwise the right half is sorted: when the target falls within that sorted range, search the right half; otherwise search the left half.
5. If the loop ends without a match, return -1.

Complexity

Time: O(log n) — Space: O(1)

Code

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid

        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

Code Explanation

How the solution above works, piece by piece.

1. At every mid, at least one of the two halves is fully sorted.
2. If nums[mid] is the target, done.
3. nums[left] <= nums[mid] means the left half is sorted. Check whether the target lies inside its range; if so search there, otherwise search the right half.
4. Otherwise the right half is sorted: same test on nums[mid] .. nums[right].
5. Checking a range is only reliable on a sorted half, which is why the code first identifies that half. Still one half discarded per step: O(log n).

Visual Walkthrough

Running it on nums = [4, 5, 6, 7, 0, 1, 2], target = 0:

Video Explanation

NeetCode — Search in Rotated Sorted Array, LeetCode 33