LeetEye LeetEye
Medium Binary Search ~5 min

Search in Rotated Sorted Array

binary-search search-in-rotated-sorted-array

Problem

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 such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]].

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.

Examples

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
Key Insight

At any midpoint, at least one half is properly sorted. Check if target is in the sorted half.

At mid, one half is sorted. Check if target is in the sorted half's range; if yes search there, else search the other half.

How to Approach This Problem

Pattern Recognition: When you see keywords like search in rotated sorted array binary-search, think Binary Search.

Step-by-Step Reasoning

1 After rotation, the array:
Answer: Has two sorted portions
[1,2,3,4,5] rotated → [4,5,1,2,3]. Both [4,5] and [1,2,3] are sorted.
2 At index mid, the left half [left...mid] is sorted if:
Answer: nums[left] <= nums[mid]
If left element ≤ mid element, the left half is in ascending order (no rotation break in this half).
3 If left half is sorted, target is in left half if:
Answer: nums[left] <= target < nums[mid]
Target must be ≥ the sorted half's minimum and < its maximum (mid) to be in that range.
4 If left half is sorted and target is NOT in left half:
Answer: Search right half
If target isn't in the sorted left, it must be in the right (if it exists).
5 If left half is NOT sorted (nums[left] > nums[mid]), then:
Answer: Right half must be sorted
One half must always be sorted. If left isn't, right is.
6 Within a sorted half, we can:
Answer: Apply standard binary search logic
A sorted portion allows normal binary search range checking.

Solution

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
        
        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1

Complexity Analysis

Time O(log n)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice Binary Search problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye