Intermediate · Module 9 · Lesson 3
Rotated sorted arrays
Identify the sorted half before eliminating.
Lesson 49 of 123
1d streakSearch in Rotated Sorted Array: Identifying the Monotonic Half
When a sorted array is rotated around a pivot, at least one half of the array (either [low, mid] or [mid, high]) remains strictly sorted. By checking whether the target falls within the sorted half, we discard half the array at each step in O(log n) time.
public int search(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] == target) return mid;
// Check if left half is sorted
if (nums[low] <= nums[mid]) {
if (target >= nums[low] && target < nums[mid]) high = mid - 1;
else low = mid + 1;
} else { // Right half is sorted
if (target > nums[mid] && target <= nums[high]) low = mid + 1;
else high = mid - 1;
}
}
return -1;
}Active Recall Checkpoint
What happens if the rotated array contains duplicate elements (e.g. [1, 0, 1, 1, 1])?
Show answer & explanation
When nums[low] == nums[mid] == nums[high], it is impossible to determine which half is sorted. The algorithm must increment low and decrement high, degrading worst-case time to O(n).
Use it when
Use when searching, finding minimums, or finding rotation counts in circular/shifted sorted arrays.
Reconsider when
Reconsider when elements are fully arbitrary or when duplicates predominate and eliminate the logarithmic partition guarantee.
Cost Model
Complexity & Trade-offs
When to use it
- Exact lookup, first/last occurrence, rotated order, and answer-space optimization.
- Any monotonic yes/no feasibility boundary.
- Implicit ordered spaces where values need not be materialized.
Common mistakes
- Mixing inclusive and half-open interval updates.
- Using binary search without proving monotonicity.
- Returning the last middle value instead of the stored boundary.
Practice prompts
- Reproduce the worked Rotated sorted arrays example without looking at the trace.
- Change one input condition and explain whether the Rotated sorted arrays invariant still holds.
- Implement the approach, derive its cost, and compare it with a straightforward baseline.
Mastery check