Hide sidebar
leetcode/DSA courseSystem Design

Search in Rotated Sorted Array

Binary SearchArrays
MediumLeetCode #33

Problem Statement

Given a rotated sorted array nums and a target value target, return the index of target if it exists in the array, or -1 if it does not exist. The array was originally sorted in ascending order before being rotated at an unknown pivot index.

Example Array

4
5
6
7
0
1
2
0
1
2
3
4
5
6
Rotation Point
Target Value
Array Values
Original sorted array: [0, 1, 2, 4, 5, 6, 7]

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

Output: 4

Explanation:

  • Array is rotated at index 4
  • Original array was [0,1,2,4,5,6,7]
  • Target 0 is found at index 4

Key Properties

  • • One half of array is always sorted
  • • Can determine which half is sorted by comparing with endpoints
  • • Target search can be narrowed to one half based on sorted portion
  • • Time complexity must be O(log n)
  • • No duplicate elements in array

Constraints

  • • 1 ≤ nums.length ≤ 5000
  • • -10^4 ≤ nums[i] ≤ 10^4
  • • All values are unique
  • • Array is rotated at some pivot
  • • -10^4 ≤ target ≤ 10^4

Algorithm Explanation

This solution uses a modified binary search that accounts for the array rotation. The key insight is that in a rotated sorted array, at least one half of the array must be sorted.

Key Steps

  • Find Mid Point: Split array into two halves.
  • Check Sorted Half: Determine which half is sorted by comparing with endpoints.
  • Target Location: Check if target lies within the sorted portion.
  • Recursive Search: Search appropriate half based on target value.

Important Properties

  • Compare nums[mid] with nums[left] to identify sorted half
  • Target range check only needed for sorted portion
  • Search space reduces by half in each iteration
  • Maintains O(log n) time complexity of binary search

Binary Search Visualization

Search for 0 in rotated sorted array

4
L
0
5
1
6
2
7
M
3
0
4
1
5
2
R
6
Start: Initialize binary search
Starting search for target 0
Step 1 of 11
Target Found
Search Range
Unsearched Area
Code Example
def search(nums: List[int], target: int) -> int:
    """
    Search for target in a rotated sorted array using binary search.
    Time complexity: O(log n)
    Space complexity: O(1)
    """
    if not nums:
        return -1
        
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        # Found target
        if nums[mid] == target:
            return mid
            
        # Check which half is sorted
        if nums[left] <= nums[mid]:
            # Left half is sorted
            if nums[left] <= target < nums[mid]:
                # Target is in left sorted half
                right = mid - 1
            else:
                # Target is in right half
                left = mid + 1
        else:
            # Right half is sorted
            if nums[mid] < target <= nums[right]:
                # Target is in right sorted half
                left = mid + 1
            else:
                # Target is in left half
                right = mid - 1
                
    return -1