Approach Summary
At each mid, determine which half is sorted. Use that to decide which half the target is in.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Linear Search (Brute Force) | O(n) | O(1) | Examine each element from index 0 to n - 1 until target is found. |
| 2 Approach 2: Modified Binary Search (Optimal) | O(log n) | O(1) | Determine which half is sorted, check if target lies within that range, and adjust boundaries. |
Step 1: Baseline
Approach 1: Linear Search (Brute Force)
Time: O(n)
Space: O(1)
Scan every element of nums sequentially. If nums[i] equals target, return i. If the end of the array is reached, return -1. While correct, it does not leverage the sorted rotation property and fails the O(log n) efficiency requirement.
Approach 1: Linear Search (Brute Force) Implementation
Approach 1: Linear Search (Brute Force)
class Solution {
public int search(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) return i;
}
return -1;
}
}class Solution {
public:
int search(vector<int>& nums, int target) {
for (int i = 0; i < (int)nums.size(); i++) {
if (nums[i] == target) return i;
}
return -1;
}
};def search(nums: list[int], target: int) -> int:
for i, num in enumerate(nums):
if num == target:
return i
return -1function search(nums, target) {
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) return i;
}
return -1;
} Step 2: Most Optimized
Approach 2: Modified Binary Search (Optimal)
Time: O(log n)
Space: O(1)
In a rotated sorted array, splitting at mid always yields at least one properly sorted half. If nums[left] <= nums[mid], the left half is monotonically increasing. We simply test if target >= nums[left] and target <= nums[mid]. If it is, target is confined to the left half, so right = mid - 1; otherwise, left = mid + 1. If the right half is sorted instead, an identical check on [nums[mid], nums[right]] guides the search.
Approach 2: Modified Binary Search (Optimal) Implementation
Approach 2: Modified Binary Search (Optimal)
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target <= nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] <= target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
}class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target <= nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] <= target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}
};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
if nums[left] <= nums[mid]:
if nums[left] <= target <= nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] <= target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1function search(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (nums[mid] === target) return mid;
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target <= nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (nums[mid] <= target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1;
}Edge Cases to Watch
- Target not present in array (returns -1)
- Single element array matching or not matching target
- Array not rotated at all (standard binary search behavior)
- Target located directly at pivot index
Algorithmic Pattern
View Pattern Guide →
Master the Binary Search Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Binary Search pattern.
Framework: Binary Search • Interview Prep: Tested at FAANG •
Explore all Binary Search problems & invariants →
How to Recognize This Pattern
- Rotated sorted array
- No pivot given
Complexity Analysis
Time Complexity
O(log n)
Space Complexity
O(1)
Tags
Array Binary Search
Frequently Asked Questions
What is the optimal time and space complexity for Search in Rotated Sorted Array?
The optimal solution for Search in Rotated Sorted Array achieves O(log n) runtime complexity and requires O(1) auxiliary space. Binary search cuts the remaining candidates in half each iteration, yielding O(log n) comparisons and O(1) space.
How do I identify that Search in Rotated Sorted Array requires the Binary Search pattern?
In technical interviews, look for key problem signals: Rotated sorted array; No pivot given. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Binary Search strategy.
What critical edge cases must be handled in Search in Rotated Sorted Array?
Essential edge cases to verify include: Target not present in array (returns -1); Single element array matching or not matching target; Array not rotated at all (standard binary search behavior); Target located directly at pivot index. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Search in Rotated Sorted Array?
Search in Rotated Sorted Array is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Facebook, LinkedIn, Microsoft.