Free lesson · DSA Mastery - Interview Prep, End to End
Search in Rotated Sorted Array
Search in Rotated Sorted Array
Search in Rotated Sorted Array opens the Modified Binary Search sub-group: a sorted array rotated at an unknown pivot, where you must still find a target in O(log n). After rotation, the array is no longer globally sorted, so the naive comparison "is the target bigger than the midpoint?" no longer tells you which half to search. The key insight rescues binary search: even after rotation, at least one half of any subarray is still sorted. So at each step you identify which half is sorted, check whether the target lies within that sorted half's range, and recurse into the appropriate side. It's binary search where each step first identifies the sorted portion before deciding which way to go. We present the linear-scan baseline and the modified binary search.
The insight: split at the midpoint. One side - either [lo, mid] or [mid, hi] - is guaranteed sorted (the pivot can only break one of them). Determine which by comparing endpoints, test whether the target falls inside that sorted side's value range, and discard the half that can't contain it.
Interactive animation: Step through every approach yourself, frame by frame, on the lesson's own examples.
The Problem
Interactive animation: The lesson's example: the input, and the answer the algorithm has to produce.
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 such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], ..., nums[k-1]].
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.
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
numsare unique. numsis an ascending array that is possibly rotated.-10^4 <= target <= 10^4
Approaches Overview
| # | Approach | Time | Space | Verdict |
|---|---|---|---|---|
| 1 | Linear scan | O(n) | O(1) | Baseline (violates O(log n)) |
| 2 | Modified binary search (identify sorted half) | O(log n) | O(1) | Optimal |
Linear scan ignores structure - O(n). The modified binary search uses the "one half is always sorted" property to decide which side to keep, achieving O(log n) despite the rotation.
Approach 1: Linear Scan
Interactive animation: Check every element, left to right.
The Idea
Scan every element; return the index when it matches the target, else -1. O(n), ignoring the rotated-sorted structure entirely.
Logic Flowchart
graph TD
A["for i = 0 .. n-1"] --> B{"nums[i] == target?"}
B -->|Yes| C["return i"]
B -->|No| D{"more?"}
D -->|Yes| A
D -->|No| E["return -1"]
style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style E fill:#dc2626,stroke:#ef4444,color:#f1f5f9
This flowchart shows the linear scan. We check each element for the target, returning its index or negative one. This is linear and ignores the structure.
Complexity
Time: O(n). Space: O(1). Binary search reaches O(log n).
Approach 2: Modified Binary Search - Optimal
Interactive animation: One half is always sorted.
The Idea
Maintain [lo, hi]. Compute mid; if nums[mid] == target, return it. Otherwise determine which half is sorted by comparing nums[lo] to nums[mid]:
- If
nums[lo] <= nums[mid], the left half is sorted. If the target lies in[nums[lo], nums[mid]), search left (hi = mid - 1); else search right (lo = mid + 1). - Otherwise the right half is sorted. If the target lies in
(nums[mid], nums[hi]], search right (lo = mid + 1); else search left (hi = mid - 1).
Each step still halves the interval, so it's O(log n).
Logic Flowchart
graph TD
A["lo=0; hi=n-1"] --> B{"lo <= hi?"}
B -->|No| C["return -1"]
B -->|Yes| D["mid = lo+(hi-lo)/2"]
D --> E{"nums[mid]==target?"}
E -->|Yes| F["return mid"]
E -->|No| G{"nums[lo] <= nums[mid]? (left sorted)"}
G -->|Yes| H{"target in [nums[lo], nums[mid])?"}
H -->|Yes| I["hi = mid-1"]
H -->|No| J["lo = mid+1"]
G -->|No| K{"target in (nums[mid], nums[hi]]?"}
K -->|Yes| L["lo = mid+1"]
K -->|No| M["hi = mid-1"]
I --> B
J --> B
L --> B
M --> B
style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style C fill:#dc2626,stroke:#ef4444,color:#f1f5f9
style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style H fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style I fill:#16a34a,stroke:#10b981,color:#f1f5f9
style J fill:#16a34a,stroke:#10b981,color:#f1f5f9
style K fill:#b45309,stroke:#f59e0b,color:#f1f5f9
style L fill:#16a34a,stroke:#10b981,color:#f1f5f9
style M fill:#16a34a,stroke:#10b981,color:#f1f5f9
This flowchart shows the modified binary search. After checking the midpoint, we determine which half is sorted by comparing the low element to the midpoint. We then test whether the target falls within the sorted half's range and search that half, otherwise the other.
Code
public static int search(int[] nums, int target) {
int lo = 0, hi = nums.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) { // left half [lo, mid] is sorted
if (nums[lo] <= target && target < nums[mid]) hi = mid - 1; // target in left
else lo = mid + 1; // else right
} else { // right half [mid, hi] is sorted
if (nums[mid] < target && target <= nums[hi]) lo = mid + 1; // target in right
else hi = mid - 1; // else left
}
}
return -1;
}
// Usage:
// search([4,5,6,7,0,1,2], 0) -> 4
// search([4,5,6,7,0,1,2], 3) -> -1
This Java code identifies the sorted half each step by comparing the low element to the midpoint, then checks whether the target lies within that half's value range to choose the direction. The interval halves each iteration.
Step-by-Step Walkthrough
A frame-by-frame trace on nums = [4,5,6,7,0,1,2], target = 0:
graph LR
F0["lo0 hi6 mid3 nums[3]=7≠0; nums[0]=4<=7 left sorted<br/>0 in [4,7)? no → lo=4"]
F1["lo4 hi6 mid5 nums[5]=1≠0; nums[4]=0<=1 left sorted<br/>0 in [0,1)? yes → hi=4"]
F2["lo4 hi4 mid4 nums[4]=0 == 0 → return 4"]
F0 --> F1 --> F2
style F0 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
This walkthrough finds zero in four, five, six, seven, zero, one, two. The left half is sorted but zero is not in its range, so we go right. Then the left half holds zero's range, so we go left, landing on zero at index four.
Result: 4.
Interactive animation: Same values, turned at a different point.
Complexity
Time: O(log n). Space: O(1).
Complexity Comparison
| Approach | Time | Space | Key Idea | When to Use |
|---|---|---|---|---|
| Linear scan | O(n) | O(1) | Check every element | Tiny inputs |
| Modified binary search | O(log n) | O(1) | Identify the sorted half, then decide | Optimal |
The modified binary search is optimal. Its defining move is to first determine which half is sorted (the rotation breaks only one half), then use that sorted half's known range to decide where the target must be. Standard binary search compares against one element; here you compare against a sorted range to handle the rotation.
Interactive animation: At n = 5000: at most 13 probes against up to 5000.
Variations & Follow-ups
Why is at least one half always sorted?
A single rotation creates exactly one "drop" point (where a larger value is followed by a smaller one). Any midpoint splits the array into two halves, and the drop can fall in only one of them - so the other half is fully sorted. By comparing nums[lo] to nums[mid], you detect which half contains the drop and which is clean, and you reason about the target using the clean half's clear ordering.
Why compare nums[lo] <= nums[mid] (with <=)?
When lo == mid (a two-element or single-element subarray), nums[lo] == nums[mid], and the left "half" is trivially sorted - the <= includes that case. With distinct values and the half-open range checks, <= correctly classifies the boundary; using strict < can misclassify tiny subarrays and cause a missed element.
Why use half-open range checks like nums[lo] <= target < nums[mid]?
Because nums[mid] was already tested (and isn't the target), the target - if in the left sorted half - must lie in [nums[lo], nums[mid]), excluding mid itself. Mirror logic gives (nums[mid], nums[hi]] for the right half. Getting these inclusive/exclusive boundaries right is the crux; an off-by-one here sends the search the wrong way.
How does this extend to duplicates? (Preview of the next problem)
With duplicates, nums[lo] == nums[mid] == nums[hi] can occur, making it impossible to tell which half is sorted. The next problem, Search in Rotated Sorted Array II, handles this by shrinking the ambiguous bounds (lo++, hi--) when endpoints tie - which degrades the worst case to O(n) but restores correctness.
What about edge cases?
- No rotation (pivot 0): The whole array is sorted; the left-sorted branch always applies, reducing to standard binary search.
- Target absent (Example 2): The interval empties → -1.
- Single element (Example 3): One comparison, returns 0 or -1.
- Target at the pivot boundary: The range checks correctly route to the half containing it.
Common Interview Pitfalls
- Comparing the target to
nums[mid]directly (as in plain binary search). Rotation breaks the global order; you must reason via the sorted half's range. - Wrong inclusive/exclusive boundaries. Use
[nums[lo], nums[mid])and(nums[mid], nums[hi]]precisely. - Strict vs non-strict
nums[lo] <= nums[mid]. The<=correctly handles the single-element sorted half. - Assuming the array is fully sorted. The rotation is the whole point; never skip the sorted-half identification.
Interactive animation: Lesson pitfall: strict vs non-strict nums[lo] <= nums[mid].
Why This Topic Matters
Search in Rotated Sorted Array is the signature modified binary search problem and a frequent interview favorite. It teaches that binary search survives a disrupted ordering as long as you can identify a locally sorted region and reason about it - a powerful generalization. The "figure out which half is clean, then decide" pattern recurs in the rotated-minimum and mountain-array problems that follow.
The next topic, Search in Rotated Sorted Array II, adds duplicates to the mix: the same rotated search, but values can repeat, which breaks the "compare endpoints to find the sorted half" logic when nums[lo] == nums[mid] == nums[hi]. The fix is to shrink the ambiguous boundary by one when ties make the sorted half indeterminate - restoring correctness at the cost of an O(n) worst case, a clean lesson in how duplicates degrade binary search guarantees.