LeetCode · #33

Search in Rotated Sorted Array Solution

Search for a target in a sorted array that has been rotated at an unknown pivot. Return its index or -1.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #33

🏗️

Pattern

Binary Search — rotated array

An array originally sorted in ascending order was rotated at some pivot. Given the rotated array nums (all elements unique) and a target, return the index of target or -1. You must achieve O(log n) runtime.

Example

 Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 // Originally [0,1,2,4,5,6,7], rotated at index 4 

Constraints

 • 1 ≤ nums.length ≤ 5000 • -10⁴ ≤ nums[i] ≤ 10⁴ • All values unique • Must run in O(log n) 

Section Two · Approach 1

Linear Scan — O(n)

Walk through the array. Correct but violates the O(log n) requirement.

Problem: O(n) ignores the partial sorted structure. In a rotated sorted array, at least one half (left or right of mid) is always sorted — binary search on that half.

Metric	Value
Time	O(n)
Space	O(1)

Section Three · Approach 2

Modified Binary Search — O(log n)

At each step, determine which half is sorted (compare nums[left] to nums[mid]). If target lies in the sorted half's range, search there. Otherwise, search the other half.

💡 Mental model: Imagine a clock with unevenly spaced numbers. At any point you look (mid), you can tell if the left half or right half goes in order. If your target number fits within the ordered half, search there. If not, go to the "chaotic" half — which will have its own ordered sub-section when you halve again.

Algorithm

Step 1: left = 0, right = n - 1.
Step 2: Compute mid. If nums[mid] == target → return mid.
Step 3: If nums[left] ≤ nums[mid] (left half sorted):
If nums[left] ≤ target < nums[mid] → right = mid - 1. Else → left = mid + 1.
Step 4: Else (right half sorted):
If nums[mid] < target ≤ nums[right] → left = mid + 1. Else → right = mid - 1.

🎯 Key insight:

A rotated sorted array always has one sorted half.
By checking nums[left] ≤ nums[mid], we identify which half is sorted.
We can then definitively decide if the target is in the sorted range — if yes, search there; if no, search the other half.

Section Four · Trace

Visual Walkthrough

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

Modified Binary Search — identify sorted half

Section Five · Implementation

Code — Java & Python

Java — Modified Binary Search

 class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) return mid;
if (nums[left] <= nums[mid]) { // left half sorted if (nums[left] <= target && target < nums[mid])
                    right = mid - 1;
else
left = mid + 1;
            } else { // right half sorted if (nums[mid] < target && target <= nums[right])
                    left = mid + 1;
else
right = mid - 1;
            }
        }
return -1;
    }
}

Python — Modified Binary Search

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

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Linear Scan	O(n)	O(1)	Ignores structure
Modified Binary Search ← optimal	O(log n)	O(1)	One sorted half always identifiable

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
No rotation	`[1,2,3,4,5]`	Standard sorted array. Left half always sorted → works normally.
Rotated by 1	`[5,1,2,3,4]`	Pivot at index 0. Right half sorted for most steps.
Single element	`[3], target=3`	mid=0, found immediately.
Target not found	`[4,5,6,7,0,1,2], target=3`	Search space exhausted → return -1.
Two elements	`[3,1], target=1`	mid=0, nums[0]=3≤nums[0] left sorted, target not in [3,3] → go right.

⚠ Common Mistake: Using < instead of ≤ in nums[left] ≤ nums[mid]. When left == mid (two-element subarray), the left "half" is a single element and is sorted. Without ≤, you'd incorrectly assume the right half is sorted and make wrong decisions.

← Back to Binary Search problems

LearningTree

LC 33 · Search in Rotated Sorted Array — Solution & Explanation | DSA Guide