Search in Rotated Sorted Array — Problem Statement & Solution Guide
Problem Description
You are given an integer array nums that was originally sorted in strictly increasing order and then rotated an unknown number of positions. The rotation preserves the relative order of elements, but the smallest element may appear at any index. Given an integer target, return the index of target in nums if it exists; otherwise, return -1. Your algorithm must run in O(log n) time, i.e., you may only use a binary‑search‑style approach.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Search in Rotated Sorted Array"
WHY DOES IT MATTER?
Understanding how to adapt binary search to rotated arrays reinforces the ability to recognize hidden order in seemingly chaotic data, a skill essential for optimizing search operations in large‑scale systems where latency matters.
OPTIMIZATION CHALLENGE
The breakthrough is realizing that one half of any sub‑array remains sorted despite rotation, allowing a constant‑time decision to discard half the search space and achieve logarithmic time.
REAL-WORLD CONNECTION
Think of a distributed log that undergoes a leader election causing a wrap‑around of indices; locating a specific entry efficiently mirrors searching in a rotated sorted array, ensuring quick recovery and consistency across nodes.
During an interview, first state the invariant (one side is sorted), then walk through the conditional logic step‑by‑step; this demonstrates both problem decomposition and clean coding discipline.
COMPLEXITY AT A GLANCE
O(log n)O(1)Core Theory — Why This Approach?
The classic "Search in Rotated Sorted Array" problem is a perfect illustration of how binary search can be adapted to handle a subtle disruption in order while preserving logarithmic efficiency. A naïve linear scan would examine each element, leading to O(n) time, which becomes prohibitive for large datasets common in production systems such as search indexes or time‑series databases. The key insight is that despite the rotation, at least one half of any sub‑array remains sorted; by comparing the target with the boundary values of the current segment, we can decide which half to discard, thereby halving the search space each iteration.
In practice, the algorithm proceeds by maintaining low and high pointers and computing a mid index. If nums[mid] equals the target, we return mid. Otherwise, we determine whether the left side (low..mid) is sorted by checking nums[low] <= nums[mid]. If it is sorted and the target lies within that range, we move high to mid‑1; otherwise, we shift low to mid+1. If the left side is not sorted, the right side must be sorted, and a symmetric check guides the pointer movement. This disciplined narrowing guarantees O(log n) time while using only constant extra space, satisfying the strict performance constraints of modern interview problems.
The optimal paradigm thus combines the divide‑and‑conquer spirit of binary search with a conditional branch that respects the rotated order. It demonstrates how algorithmic invariants—here, the guarantee of at least one sorted half—can be leveraged to transform a seemingly broken structure back into a tractable form, a technique that recurs across many advanced data‑structure challenges.
Interview Questions on This Problem
Q1How would you modify binary search to find a target in a rotated sorted array without using extra space?
Identify which half of the current search interval is sorted by comparing nums[low] and nums[mid]; then decide if the target lies within that sorted half. If it does, adjust the high pointer to mid‑1; otherwise, move the low pointer to mid+1. Repeat until the target is found or the interval is empty.
Q2What is the time complexity of searching for a target in a rotated sorted array and why does it remain logarithmic?
The time complexity is O(log n) because each iteration discards half of the remaining elements, just like standard binary search. The rotation does not affect the halving property because at least one side of any sub‑array is guaranteed to be sorted, allowing a deterministic choice of which half to eliminate.
Q3Can the algorithm be extended to handle arrays with duplicate values? If so, what changes are required?
With duplicates, the simple sorted‑half check may fail when nums[low] == nums[mid] == nums[high]. In that case, increment low and decrement high to shrink the search window, or use a more robust approach like finding the pivot first with O(log n) average but O(n) worst‑case. The core idea remains, but extra handling for equal edge values is needed.
Examples
Input
nums = [15, 18, 2, 3, 6, 12], target = 3
Output
3
Explanation: The original sorted order is [2,3,6,12,15,18]; after rotating right by two positions we obtain the given array. Binary search examines the middle element (index 2, value 2). Since target 3 > 2 and the right half [3,6,12] is sorted, the algorithm continues in that half and finds target at index 3.
Input
nums = [7, 9, 11, 13, 1, 3, 5], target = 13
Output
3
Explanation: Midpoint is index 3 (value 13), which matches the target, so the search terminates immediately with index 3.
Input
nums = [22, 25, 1, 5, 7, 9, 12, 15, 18], target = 22
Output
0
Explanation: Midpoint (index 4, value 7) lies in the right‑sorted segment. Because target 22 > 7, the algorithm discards the right half and searches the left half [22,25,1]. The new midpoint (index 1, value 25) is greater than target, so the left half [22] is examined, yielding index 0.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- All elements in nums are distinct
- nums was sorted in strictly increasing order before rotation
- -10^9 <= target <= 10^9
Optimal Approach & Strategy
Apply a modified binary search that determines which half of the current interval is sorted and discards the other half based on the target's value, achieving logarithmic time.
Brute Force Approach
Iterate through the array from start to finish, comparing each element with the target; return the index when found or -1 after the loop.
Verified Code Solutions
function search(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 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;
}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;
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(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;
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, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 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) {
let mid = Math.floor((left + right) / 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;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.