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

Constraints

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

View original on LeetCode ↗

Linear Scan

Time O(n)Space O(1)

Just walk the array looking for the target. It works regardless of rotation, but it throws away the fact that the array is built from two sorted runs, which is what the O(log n) requirement is pushing you toward.

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        for i, num in enumerate(nums):
            if num == target:
                return i
        return -1

Binary Search With a Sorted-Half Check

OptimalTime O(log n)Space O(1)

A rotated sorted array always splits at mid into one half that is genuinely sorted and one half that still contains the rotation point. Figure out which half is sorted by comparing nums[lo] to nums[mid]. Then check whether target falls inside that sorted half’s range — if it does, recurse into it as usual; if it does not, the target (if it exists at all) must be in the other, still-rotated half.

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[lo] <= nums[mid]:
                # left half [lo, mid] is sorted
                if nums[lo] <= target < nums[mid]:
                    hi = mid - 1
                else:
                    lo = mid + 1
            else:
                # right half [mid, hi] is sorted
                if nums[mid] < target <= nums[hi]:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return -1

Tracing nums = [4,5,6,7,0,1,2], target = 0:

Watch one nums[lo] versus nums[mid] comparison identify the sorted half, then the range test against that half decide which pointer moves and which indices get struck out.

Array

Decision

mid—

sorted half—

range test—

action—

1 / 9

comparingcurrentdiscardedresult

A rotated sorted array is two sorted runs, so one half of every split is sorted. Finding that half is what keeps each probe O(1).

Why it’s correct: whichever half is sorted, its endpoints give a valid range to test membership in O(1); if the target is not in that range it cannot be in that half (since that half is fully sorted and bounded), so the other half is safe to search next — no candidate index is ever discarded incorrectly. Complexity: the search window halves every iteration, giving O(log n) time, O(1) space.

Search In Rotated Sorted Array

Linear Scan

Binary Search With a Sorted-Half Check

More Binary Search practice