How Do You Search in a Rotated Sorted Array?
Learn the modified binary search technique to search a rotated sorted array in O(log n) time and answer this interview question well.
Expected Interview Answer
Searching a rotated sorted array for a target in O(log n) works by running a modified binary search: at each step, determine which half (left or right of mid) is properly sorted, then check whether the target lies within that sorted half's range to decide which side to discard.
Because the array was sorted then rotated at some unknown pivot, standard binary search alone breaks since the array is not globally monotonic. The fix is to compare nums[left] with nums[mid] to detect which half is sorted: if nums[left] <= nums[mid], the left half is sorted, so check if target falls in [nums[left], nums[mid]) to decide whether to search left or right; otherwise the right half is sorted, so check if target falls in (nums[mid], nums[right]]. This preserves O(log n) time by still halving the search space every iteration, just with an extra sorted-half determination before deciding direction. The technique extends to arrays with duplicates, though duplicates can force an O(n) worst case since sortedness can become ambiguous.
- O(log n) time despite the rotation, same order as plain binary search
- O(1) extra space, purely pointer-based
- Generalizes to finding the rotation pivot itself
- A single well-understood pattern reused across many rotated-array problems
AI Mentor Explanation
Searching a rotated sorted array is like looking for a specific over number in a highlights reel that was sorted chronologically, then spliced so the back half plays before the front half. At the midpoint clip, you check whether the segment from the start to the midpoint is still in proper chronological order; if it is, you know whether the target over falls inside that clean segment or must be in the other, still-rotated segment. If the front segment is the rotated one instead, you apply the same over-range check to the back segment, which is the properly ordered one. Either way, you discard half the reel every time, keeping the search just as fast as a normal binary search through an unspliced highlights reel.
Step-by-Step Explanation
Step 1
Set up standard binary search pointers
Initialize left = 0, right = n - 1, and loop while left <= right, computing mid each iteration.
Step 2
Determine which half is sorted
Compare nums[left] with nums[mid]: if nums[left] <= nums[mid], the left half is sorted; otherwise the right half is sorted.
Step 3
Check if target lies in the sorted half
If the sorted half contains the target range, narrow the search to that half; otherwise search the other half.
Step 4
Repeat until found or pointers cross
Continue halving the search space each iteration, returning the index on a match or -1 if the loop ends without one.
What Interviewer Expects
- Correctly identify why plain binary search fails on a rotated array
- Explain how to determine which half is sorted using nums[left] vs nums[mid]
- State the target-range check that decides which half to discard
- State O(log n) time, O(1) space, and mention the duplicate-handling edge case
Common Mistakes
- Using nums[left] < nums[mid] instead of <=, mismatching the two-element case
- Forgetting to check whether target is within the sorted half's bounds before discarding
- Not handling duplicates, which can make sortedness ambiguous and require a linear fallback
- Off-by-one errors in the range checks (< vs <=) when comparing against nums[left] or nums[right]
Best Answer (HR Friendly)
“To search a rotated sorted array in log time, I still do binary search, but at each step I first figure out which half of the array is properly sorted, then check whether the target falls in that half's range. If it does, I search that half; if not, I search the other half. That extra sorted-half check is the only difference from a normal binary search, and it still cuts the search space in half every time.”
Code Example
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]:
# Left half is sorted
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
# Right half is sorted
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
print(search([4, 5, 6, 7, 0, 1, 2], 0)) # 4Follow-up Questions
- How would you find the minimum element in a rotated sorted array?
- How does the algorithm change if the array contains duplicate values?
- How would you find the rotation pivot index itself?
- How would you adapt this to search a rotated sorted array of unknown length?
MCQ Practice
1. What is the time complexity of searching a rotated sorted array using the modified binary search technique?
Each iteration still eliminates half the search space, preserving the O(log n) bound of standard binary search.
2. How do you determine which half of the array is properly sorted at each step?
If nums[left] <= nums[mid], the left half from left to mid is sorted; otherwise the right half from mid to right is sorted.
3. What can duplicate values in a rotated sorted array force in the worst case?
When nums[left] == nums[mid] == nums[right], you cannot tell which half is sorted, forcing a linear shrink of the search bounds.
Flash Cards
What breaks plain binary search on a rotated sorted array? — The array is no longer globally monotonic, so a single left/right comparison against the target is not enough.
How do you decide which half of a rotated sorted array is sorted? — Compare nums[left] with nums[mid]: if nums[left] <= nums[mid], the left half is sorted.
What is the time complexity of rotated sorted array search? — O(log n), same as standard binary search, since half the array is discarded each step.
What edge case can degrade rotated sorted array search to O(n)? — Duplicate values that make it ambiguous which half is sorted.