60. Search in Rotated Sorted Array
🔗 LeetCode Problem: 33. Search in Rotated Sorted Array
📊 Difficulty: Medium
🏷️ Topics: Array, Binary Search
Problem Statement
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
- -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
🎨 Visual Understanding
The Problem Visualized
Original sorted array:
[0, 1, 2, 4, 5, 6, 7]
Rotated at pivot index 3:
[4, 5, 6, 7, 0, 1, 2]
↑ ↑
pivot rotation point
The array has TWO sorted halves:
Left half: [4, 5, 6, 7] - sorted
Right half: [0, 1, 2] - sorted
Example: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Visual:
Index: 0 1 2 3 4 5 6
Value: 4 5 6 7 0 1 2
↑
target = 0 at index 4
Different rotation scenarios:
No rotation:
[0, 1, 2, 4, 5, 6, 7] - completely sorted
Rotated at index 1:
[7, 0, 1, 2, 4, 5, 6]
↑ ↑
pivot
Rotated at index 4:
[4, 5, 6, 7, 0, 1, 2]
↑ ↑
pivot
Rotated at index 6:
[2, 4, 5, 6, 7, 0, 1]
↑ ↑
pivot
🚨 CRITICAL INSIGHT - Why Modified Binary Search Works
The Key Pattern!
A rotated sorted array has a special property:
At LEAST ONE half is always SORTED!
Example: [4, 5, 6, 7, 0, 1, 2]
Check mid = 7 (index 3)
Left half: [4, 5, 6, 7] - SORTED ✓
Right half: [0, 1, 2] - SORTED ✓
Key Insight:
At any mid point, at least one side is sorted
We can use the sorted side to decide where to search!
How?
1. Find mid
2. Determine which half is sorted
3. Check if target is in the sorted half
4. If yes: search that half
5. If no: search the other half
This still eliminates half each time = O(log n)!
How to Identify the Sorted Half
Compare nums[left] with nums[mid]:
Case 1: nums[left] <= nums[mid]
Left half is sorted
[4, 5, 6, 7, 0, 1, 2]
↑ ↑
left mid
4 <= 7, so left half [4,5,6,7] is sorted ✓
Case 2: nums[left] > nums[mid]
Right half is sorted
[6, 7, 0, 1, 2, 4, 5]
↑ ↑
left mid
6 > 1, so right half [1,2,4,5] is sorted ✓
Why this works?
If no rotation in left half: nums[left] <= nums[mid]
If rotation in left half: nums[left] > nums[mid]
Rotation point causes a "drop" in values
The side without drop is sorted!
Decision Making After Finding Sorted Half
Once we know which half is sorted:
Check if target is in that sorted range
If LEFT half is sorted [left...mid]:
If nums[left] <= target < nums[mid]:
Target is in left half
Search left: right = mid - 1
Else:
Target must be in right half
Search right: left = mid + 1
If RIGHT half is sorted [mid...right]:
If nums[mid] < target <= nums[right]:
Target is in right half
Search right: left = mid + 1
Else:
Target must be in left half
Search left: right = mid - 1
Example: [4, 5, 6, 7, 0, 1, 2], target = 0
Mid = 7 (index 3)
Left half [4,5,6,7] is sorted
Is 0 in [4, 7]? No! (0 < 4)
So search right half [0, 1, 2]
Found at index 4! ✓
🎯 Approach 1: Linear Search (Brute Force)
The Most Natural Thinking 💭
Core Logic:
Ignore the rotation, just check each element:
If element equals target, return index
If reach end, return -1
Implementation
public int search(int[] nums, int target) {
// Check each element
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
return i;
}
}
return -1; // Not found
}
⏰ Time: O(n) - Check every element
💾 Space: O(1) - Only variables
❌ Problem: Doesn't meet O(log n) requirement! Doesn't use sorted property!
🎯 Approach 2: Modified Binary Search (Optimal) ⭐
Better Approach 💡
🧠 The Core Insight
Key Observation:
At least one half is ALWAYS sorted
Strategy:
1. Find which half is sorted
2. Check if target is in sorted half
3. Search appropriate half
4. Repeat until found or exhausted
Still O(log n) because we eliminate half each time!
The Strategy:
Modified Binary Search:
1. Calculate mid
2. Check if nums[mid] == target (found!)
3. Determine which half is sorted:
- If nums[left] <= nums[mid]: left half sorted
- Else: right half sorted
4. Check if target in sorted half:
- If yes: search that half
- If no: search other half
5. Repeat
Implementation
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
// Found target
if (nums[mid] == target) {
return mid;
}
// Determine which half is sorted
if (nums[left] <= nums[mid]) {
// Left half is sorted [left...mid]
// Check if target is in sorted left half
if (nums[left] <= target && target < nums[mid]) {
// Target in left half
right = mid - 1;
} else {
// Target in right half
left = mid + 1;
}
} else {
// Right half is sorted [mid...right]
// Check if target is in sorted right half
if (nums[mid] < target && target <= nums[right]) {
// Target in right half
left = mid + 1;
} else {
// Target in left half
right = mid - 1;
}
}
}
return -1; // Not found
}
⏰ Time: O(log n) - Modified binary search
💾 Space: O(1) - Only pointers
🔍 Dry Run
Example 1: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Goal: Find 0 in rotated array
Initial: left = 0, right = 6
[4, 5, 6, 7, 0, 1, 2]
↑ ↑
left right
Iteration 1:
mid = 0 + (6 - 0) / 2 = 3
nums[3] = 7
7 ≠ 0
Is left half sorted?
nums[0] = 4 <= nums[3] = 7 ✓
Left half [4, 5, 6, 7] is sorted
Is target in left half [4, 7]?
4 <= 0? NO (0 < 4)
Target NOT in left half
Search right half
left = 4
[4, 5, 6, 7, 0, 1, 2]
↑ ↑
left right
Iteration 2:
mid = 4 + (6 - 4) / 2 = 5
nums[5] = 1
1 ≠ 0
Is left half sorted?
nums[4] = 0 <= nums[5] = 1 ✓
Left half [0, 1] is sorted
Is target in left half [0, 1]?
0 <= 0 < 1 ✓ YES!
Target in left half
Search left half
right = 4
[4, 5, 6, 7, 0, 1, 2]
↑ ↑
right left
Iteration 3:
mid = 4 + (4 - 4) / 2 = 4
nums[4] = 0
0 == 0 ✓ FOUND!
return 4 ✓
Example 2: nums = [4, 5, 6, 7, 0, 1, 2], target = 3
Goal: Find 3 in rotated array
Initial: left = 0, right = 6
[4, 5, 6, 7, 0, 1, 2]
↑ ↑
left right
Iteration 1:
mid = 3, nums[3] = 7
7 ≠ 3
Left half [4,5,6,7] sorted
Is 3 in [4, 7]? NO (3 < 4)
Search right
left = 4
Iteration 2:
mid = 5, nums[5] = 1
1 ≠ 3
Left half [0,1] sorted
Is 3 in [0, 1]? NO (3 > 1)
Search right
left = 6
Iteration 3:
mid = 6, nums[6] = 2
2 ≠ 3
Left half [2] sorted (single element)
Is 3 in [2, 2]? NO
Search right
left = 7
Loop ends (left > right)
return -1 ✓
Example 3: nums = [1], target = 0
Single element case
Initial: left = 0, right = 0
[1]
↑
left/right
Iteration 1:
mid = 0
nums[0] = 1
1 ≠ 0
Left half sorted (1 <= 1)
Is 0 in [1, 1]? NO
Search right
left = 1
Loop ends (left > right)
return -1 ✓
Example 4: nums = [7, 0, 1, 2, 4, 5, 6], target = 0
Rotated at beginning
Initial: left = 0, right = 6
[7, 0, 1, 2, 4, 5, 6]
↑ ↑
left right
Iteration 1:
mid = 3, nums[3] = 2
2 ≠ 0
Is left half sorted?
nums[0] = 7 > nums[3] = 2 ✗
Right half [2,4,5,6] is sorted
Is 0 in [2, 6]? NO (0 < 2)
Search left
right = 2
Iteration 2:
mid = 1, nums[1] = 0
0 == 0 ✓ FOUND!
return 1 ✓
🎯 Why This Works - Deep Dive
The Sorted Half Property:
═══════════════════════════════════════════════════════════════
In rotated sorted array:
Original: [0, 1, 2, 4, 5, 6, 7]
Rotated: [4, 5, 6, 7, 0, 1, 2]
└─sorted─┘ └─sorted─┘
At ANY mid point:
At least one half has no rotation
That half is completely sorted!
Why?
Rotation happens at ONE point
Can't affect both halves at same time
So one half is always unbroken (sorted)
Identifying Sorted Half:
═══════════════════════════════════════════════════════════════
Method: Compare nums[left] with nums[mid]
If nums[left] <= nums[mid]:
No drop in left half
Left half is sorted
Example: [4, 5, 6, 7, 0, 1, 2]
↑ ↑
4 <= 7, left sorted
If nums[left] > nums[mid]:
Drop in left half (rotation point)
Right half is sorted
Example: [6, 7, 0, 1, 2, 4, 5]
↑ ↑
6 > 1, right sorted
Searching in Sorted Half:
═══════════════════════════════════════════════════════════════
Once we identify sorted half:
Use normal binary search logic for that half
If target in sorted range:
Search that half
Else:
Target must be in other half
This still eliminates half each time!
Edge Case: nums[left] == nums[mid]
═══════════════════════════════════════════════════════════════
Since all values are UNIQUE:
nums[left] == nums[mid] means left == mid
This happens when search space is very small
We handle it naturally:
If nums[left] <= nums[mid]: true
Treat as left half sorted
Works correctly!
Why Still O(log n)?
═══════════════════════════════════════════════════════════════
Each iteration:
Find mid: O(1)
Determine sorted half: O(1)
Check target range: O(1)
Eliminate half: search space / 2
Total iterations: log₂(n)
Time: O(log n) ✓
The Algorithm Summary
Step-by-Step Logic:
1. Calculate mid
2. If nums[mid] == target: FOUND! return mid
3. Determine sorted half:
If nums[left] <= nums[mid]:
LEFT half is sorted
Else:
RIGHT half is sorted
4. Check if target in sorted half:
If LEFT sorted:
If nums[left] <= target < nums[mid]:
Target in left → right = mid - 1
Else:
Target in right → left = mid + 1
If RIGHT sorted:
If nums[mid] < target <= nums[right]:
Target in right → left = mid + 1
Else:
Target in left → right = mid - 1
5. Repeat until found or left > right
⚠️ Common Mistakes to Avoid
Mistake 1: Wrong comparison for sorted half
// ❌ WRONG - Using strict inequality
if (nums[left] < nums[mid]) {
// Fails when left == mid
}
// ✓ CORRECT - Use <=
if (nums[left] <= nums[mid]) {
// Handles all cases
}
Mistake 2: Wrong target range check
// ❌ WRONG - Not including boundaries
if (nums[left] < target && target < nums[mid]) {
// Misses target at boundaries!
}
// ✓ CORRECT - Include boundaries
if (nums[left] <= target && target < nums[mid]) {
// Checks full range
}
Mistake 3: Checking both halves for sorted
// ❌ WRONG - Redundant and confusing
if (nums[left] <= nums[mid]) {
// left sorted logic
}
if (nums[mid] <= nums[right]) {
// right sorted logic
}
// ✓ CORRECT - Use if-else
if (nums[left] <= nums[mid]) {
// left sorted
} else {
// right sorted (guaranteed)
}
Mistake 4: Forgetting to update pointers
// ❌ WRONG - Doesn't move pointers
if (target in range) {
// ... but no pointer update!
}
// ✓ CORRECT - Always update
if (target in range) {
right = mid - 1;
} else {
left = mid + 1;
}
Mistake 5: Trying to find pivot first
// ❌ INEFFICIENT - Two pass approach
// 1. Find pivot index
// 2. Binary search in correct half
// ✓ EFFICIENT - One pass
// Find sorted half and search in one go
🎯 Pattern Recognition
Problem Type: Binary Search - Rotated Array
Core Pattern: Modified Binary Search with Sorted Half Detection
When to Apply:
✓ Array is SORTED but ROTATED
✓ Need to find specific element
✓ All values unique
✓ Need O(log n) time
✓ Don't know rotation point
Recognition Keywords:
- "Rotated sorted array"
- "Possibly rotated"
- "Pivot index"
- "Find target"
- "O(log n) runtime"
- Distinct/unique values
Similar Problems:
- Find Minimum in Rotated Sorted Array (LC 153)
- Search in Rotated Sorted Array II (LC 81) - with duplicates
- Find Peak Element (LC 162)
Key Difference from Classic BS:
┌────────────────────────────────────────────┐
│ Classic Binary Search: │
│ - Entire array is sorted │
│ - Simple mid comparison │
│ │
│ Rotated Array (This Problem): │
│ - Array is rotated (2 sorted parts) │
│ - First identify sorted half │
│ - Then check if target in sorted range │
│ - More complex decision logic │
└────────────────────────────────────────────┘
The "identify sorted half" is the KEY difference!
🧠 Interview Strategy
Step 1: "Rotated sorted array → Modified Binary Search"
Step 2: "At least one half is always sorted"
Step 3: "Identify which half is sorted"
Step 4: "Check if target in sorted half's range"
Step 5: "Search appropriate half"
Key Points to Mention:
- Recognize rotated array pattern
- Key insight: one half always sorted
- Compare nums[left] vs nums[mid] to identify
- Check target range in sorted half
- Standard pointer updates (mid ± 1)
- Still O(log n) - eliminate half each time
- Time: O(log n), Space: O(1)
- Handle edge cases: single element, no rotation
Why This Approach?
"The array is sorted but rotated. The key insight is that at any
mid point, at least one half must be completely sorted. I can
identify which half by comparing nums[left] with nums[mid]. If
nums[left] <= nums[mid], the left half is sorted, otherwise the
right half is sorted. Once I know which half is sorted, I can use
standard binary search logic: check if the target falls within
the sorted half's range. If yes, search that half. If no, search
the other half. This still maintains O(log n) because we eliminate
half the search space each iteration."
Edge Cases to Mention:
✓ No rotation (already sorted)
✓ Single element
✓ Target at rotation point
✓ Target not in array
📝 Quick Revision Notes
🎯 Core Concept:
Rotated Sorted Array Search: Use modified binary search. Key insight: at least ONE half is always sorted. Identify sorted half (nums[left] <= nums[mid]), check if target in that range, search appropriately. Still O(log n)!
⚡ Quick Implementation:
class Test {
public int search(int[] a, int k) {
int left = 0;
int right = a.length - 1;
int index = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
// Just return if you found the number
if(a[mid] == k) {
return mid;
}
// At any time, atleast 1 half would be definetely sorted.
// Identify that half
// Why search in sorted half? We will come to know definetely if the element
// being searched (k) would be present or not as its sorted.
// Below if-else looks redundant at the first sight. But they are necessary if the
// element is not present in the array
if(a[left] <= a[mid]) { // left half sorted. <= needed for an edge case of finding 1 in [3, 1]
// check if the number exists in this sorted left
if(a[left] <= k && k < a[mid]) {
// search in this half alone.
right = mid - 1;
} else {
// search in other half.
left = mid + 1;
}
} else { // right half sorted
if(a[mid] < k && k <= a[right]) {
// update left
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return index;
}
public static void main(String[] args) {
Test t = new Test();
System.out.println(t.search(new int[] {4,5,6,7,0,1,2}, 0) == 4);
System.out.println(t.search(new int[] {4,5,6,7,0,1,2}, 3) == -1);
System.out.println(t.search(new int[] {1, 2, 3, 4, 5}, 3) == 2);
System.out.println(t.search(new int[] {5}, 5) == 0);
System.out.println(t.search(new int[] {5}, 3) == -1);
System.out.println(t.search(new int[] {3, 1}, 1) == 1);
}
}
🔑 Key Insights:
- Pattern: Modified Binary Search for Rotated Array
- Key Property: At least ONE half always sorted
- Identify Sorted:
nums[left] <= nums[mid]→ left sorted - Check Range: Target in sorted half's range?
- Decision: Search sorted half if in range, else other half
- Still O(log n): Eliminate half each iteration
- Unique Values: Critical assumption
- Loop:
left <= right(standard) - Time: O(log n), Space: O(1)
🎪 Memory Aid:
"One half sorted, always! Find it, check range, search smart!"
Think: "Compare left-mid → Find sorted → Check target → Decide!"
💡 The Key Insight:
Two critical checks:
1. Which half is sorted?
if (nums[left] <= nums[mid])
→ Left sorted
else
→ Right sorted
2. Is target in sorted half?
Left sorted: nums[left] <= target < nums[mid]
Right sorted: nums[mid] < target <= nums[right]
⚠️ Critical Details:
1. Identify sorted: nums[left] <= nums[mid] ← Use <=
2. Left range: nums[left] <= target < nums[mid] ← Include left
3. Right range: nums[mid] < target <= nums[right] ← Include right
4. Update: mid ± 1 (standard)
5. Loop: while (left <= right)
6. Return: mid or -1
🔥 The Decision Tree:
At each mid:
├─ nums[mid] == target? → return mid ✓
├─ nums[left] <= nums[mid]? (left sorted)
│ ├─ target in [left, mid)? → right = mid - 1
│ └─ else → left = mid + 1
└─ else (right sorted)
├─ target in (mid, right]? → left = mid + 1
└─ else → right = mid - 1
💡 Why It Works:
Rotated array = Two sorted subarrays
Example: [4, 5, 6, 7, 0, 1, 2]
└─sorted─┘ └─sorted─┘
At ANY mid, one half has no break
That half is completely sorted
Use that sorted property!
Still eliminate half each time
= O(log n) ✓
🎯 Visual Pattern:
[4, 5, 6, 7, 0, 1, 2]
↑ ↑ ↑
left mid right
nums[left]=4 <= nums[mid]=7
→ Left half [4,5,6,7] is sorted
Is target in [4, 7)?
Yes → search left
No → search right
🧪 Edge Cases
Case 1: No rotation
Input: nums = [1, 2, 3, 4, 5], target = 3
Output: 2
(Degrades to classic binary search)
Case 2: Single element - found
Input: nums = [5], target = 5
Output: 0
Case 3: Single element - not found
Input: nums = [5], target = 3
Output: -1
Case 4: Two elements - rotated
Input: nums = [3, 1], target = 1
Output: 1
Case 5: Target at rotation point
Input: nums = [4, 5, 6, 7, 0, 1, 2], target = 0
Output: 4
Case 6: Rotated at beginning
Input: nums = [7, 0, 1, 2, 4, 5, 6], target = 0
Output: 1
Case 7: Rotated at end
Input: nums = [2, 4, 5, 6, 7, 0, 1], target = 2
Output: 0
All handled correctly! ✓
Related Patterns
- Find Minimum in Rotated Sorted Array (LC 153) - Similar logic, find pivot
- Search in Rotated Sorted Array II (LC 81) - With duplicates (harder)
- Find Peak Element (LC 162) - Similar half-elimination strategy
Happy practicing! 🎯
Note: This is a classic MAANG interview problem! The key is recognizing that one half is always sorted. Master this pattern - it appears frequently!