Search in Rotated Sorted Array

Difficulty: Medium
Topics: Array, Binary Search
Link: https://leetcode.com/problems/search-in-rotated-sorted-array/

Problem Description

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 (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 rotated at pivot index 3 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
-104 <= nums[i] <= 104
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-104 <= target <= 104

Solution

1. Problem Deconstruction

Technical Restatement
Given a rotated sorted array of distinct integers, determine the index of a target element in O(log n) time. The array is split at an unknown pivot and rotated, resulting in two ascending subarrays.

Beginner Explanation
Imagine a list of numbers sorted from small to large, but someone cut it into two parts and swapped their order. Your task is to find a specific number in this modified list as quickly as possible, without checking every single number.

Mathematical Formulation
Let A be an array of distinct integers such that for some pivot k, A[k], A[k+1], ..., A[n-1], A[0], A[1], ..., A[k-1] is sorted. Find i where A[i] = target.

Constraint Analysis

Distinct values: Enables binary search without ambiguity.
Length ≤ 5000: Allows O(n) solutions but mandates O(log n) for optimality.
Rotated sorted structure: The array has exactly one “drop” point where A[i] > A[i+1].
Edge cases:
- Array fully sorted (no rotation).
- Target is the pivot element.
- Single-element array.

2. Intuition Scaffolding

Real-World Analogy
Like searching for a word in a dictionary that was split into two halves and reordered. You first check if the word lies in the first half (alphabetically) or the second.

Gaming Analogy
In a game with two sorted treasure lists merged at a hidden point, quickly narrow down the treasure’s location by eliminating impossible halves.

Math Analogy
The problem reduces to partitioning the array into two monotonic functions and applying binary search on the appropriate partition.

Common Pitfalls

Assuming the array is unrotated and using vanilla binary search.
Incorrectly identifying the sorted half (e.g., using nums[mid] ≤ nums[high] to check right half).
Missing equality in comparisons (e.g., target < nums[mid] vs. target ≤ nums[mid]).
Not handling single-element or two-element edge cases.
Failing to account for all possible target locations across the pivot.

3. Approach Encyclopedia

Optimal Approach: Modified Binary Search
Pseudocode

def search(nums, target):
    low, high = 0, len(nums) - 1
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        # Check if left half is sorted
        if nums[low] <= nums[mid]:
            if nums[low] <= target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1
        else:  # Right half is sorted
            if nums[mid] < target <= nums[high]:
                low = mid + 1
            else:
                high = mid - 1
    return -1

Complexity Proof

Time: Each iteration halves the search space → O(log n).
Space: Constant variables → O(1).

Visualization

Original: [4,5,6,7,0,1,2], target=0  
Step 1: mid=3 (7). Left sorted [4,5,6,7]. 0 not in range → search right.  
Step 2: mid=5 (1). Left [0,1] sorted. 0 in range → search left.  
Step 3: mid=4 (0). Found.

4. Code Deep Dive

Line-by-Line Annotations

def search(nums, target):
    low, high = 0, len(nums) - 1  # Initialize binary search bounds
    while low <= high:  # Standard binary search loop
        mid = (low + high) // 2  # Compute midpoint
        if nums[mid] == target:  # Early exit if found
            return mid
        if nums[low] <= nums[mid]:  # Left half is sorted
            # Check if target is within left's bounds
            if nums[low] <= target < nums[mid]:
                high = mid - 1  # Narrow to left
            else:
                low = mid + 1  # Target in unsorted right
        else:  # Right half is sorted
            # Check if target is within right's bounds
            if nums[mid] < target <= nums[high]:
                low = mid + 1  # Narrow to right
            else:
                high = mid - 1  # Target in unsorted left
    return -1  # Target not found

Edge Case Handling

Example 3 (nums=[1], target=0): Loop exits after one iteration (mid=0), returns -1.
Single-element array: Handled by initial loop check.

5. Complexity War Room

Hardware-Aware Analysis

At 5000 elements, binary search requires ~13 iterations (log2(5000) ≈ 12.3). Minimal memory footprint (three integers).

Industry Comparison Table

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n)	O(1)	10/10	❌ Not O(log n)
Binary Search	O(log n)	O(1)	8/10	✅ Optimal

6. Pro Mode Extras

Variants

Two Transactions (LC 123): Track buy/sell points with dynamic programming.
Allow Duplicates (LC 81): Requires worst-case O(n) time due to equality checks.

Interview Cheat Sheet

Always mention binary search adaptations for rotated arrays.
Clarify edge cases (e.g., fully sorted, single-element).
Walk through examples to verify logic.

#33 - Search in Rotated Sorted Array