Search in Rotated Sorted Array
Asked at Google, Meta, Oracle, Salesforce, Walmart
Problem
Given a sorted array that has been rotated at some pivot, find the index of a target value. The array has no duplicates. This problem tests your ability to modify binary search for a non-standard condition.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Oracle | Medium | View all Oracle questions → |
| Salesforce | Medium | View all Salesforce questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
The array is rotated, but at least one half is always sorted. Use that property to decide which half to search.
Compare nums[mid] with nums[left]. If nums[left] <= nums[mid], the left half is sorted. Otherwise the right half is sorted.
If the left half is sorted: check if target is in [nums[left], nums[mid]). If yes, search left. If no, search right.
If the right half is sorted: check if target is in (nums[mid], nums[right]]. If yes, search right. If no, search left.
Visual walkthrough for [4,5,6,7,0,1,2], target=0:
lo=0, hi=6, mid=3. nums[3]=7 > nums[0]=4 → left half sorted.
Target 0 not in [4,7) → search right. lo=4.
lo=4, hi=6, mid=5. nums[5]=1 < nums[6]=2 → right half sorted.
Target 0 not in (1,2] → search left. hi=4.
lo=4, hi=4, mid=4. nums[4]=0 == target! Return 4.
Edge cases: target not found (return -1), single element (return 0 or -1), target at pivot point.
Optimal Approach
Binary search with a twist:
Step 1: Find mid = (lo + hi) // 2.
Step 2: If nums[mid] == target, return mid.
Step 3: Determine which half is sorted:
- If nums[lo] <= nums[mid]: left half is sorted
- Else: right half is sorted
Step 4: Check if target is in the sorted half:
- Left sorted: if nums[lo] <= target < nums[mid], search left; else search right
- Right sorted: if nums[mid] < target <= nums[hi], search right; else search left
The key insight: in a rotated sorted array without duplicates, one half is always sorted. You can always determine which half by comparing nums[lo] and nums[mid].
Time: O(log n). Space: O(1).
What Trips People Up in Real Interviews
Confusing this with binary search on a sorted array. The array is rotated, so you can't just check if target is between low and high. You need to determine which half is sorted.
Not handling the case where the target is in the unsorted half. Always check which half is sorted first, then determine if the target is in that half.
Forgetting that one half is always sorted. In a rotated sorted array, at least one of the two halves (left or right of mid) is guaranteed to be sorted.
Not handling duplicates. If the problem says duplicates are allowed, the approach changes (you can't always determine which half is sorted).
Using <= instead of < when checking which half is sorted. nums[lo] <= nums[mid] correctly identifies a sorted left half even when lo == mid. Using < breaks with 2-element arrays.
Solution Code
def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1Frequently Asked Questions
What is the Search in Rotated Sorted Array problem?
Given a sorted array that has been rotated at some pivot, find the index of a target value. The array has no duplicates. This problem tests your ability to modify binary search for a non-standard condition.
How do you solve Search in Rotated Sorted Array?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Search in Rotated Sorted Array?
Search in Rotated Sorted Array is asked at Google, Meta, Oracle, Salesforce, Walmart. It is a medium difficulty problem.
What are common mistakes on Search in Rotated Sorted Array?
- Confusing this with binary search on a sorted array. The array is rotated, so you can't just check if target is between low and high. You need to determine which half is sorted.
- Not handling the case where the target is in the unsorted half. Always check which half is sorted first, then determine if the target is in that half.
- Forgetting that one half is always sorted. In a rotated sorted array, at least one of the two halves (left or right of mid) is guaranteed to be sorted.
- Not handling duplicates. If the problem says duplicates are allowed, the approach changes (you can't always determine which half is sorted).
- Using <= instead of < when checking which half is sorted. `nums[lo]` <= `nums[mid]` correctly identifies a sorted left half even when lo == mid. Using < breaks with 2-element arrays.